Friday, March 7th, 2003
11:30am - 12:30pm, in Science 1- Small Auditorium

Jozef Skokan

University of Illinois at Urbana-Champaign

Applications of the Regularity Method

Abstract: While many basic combinatorial results are obtained by ingenuity and detailed reasoning, the modern theory relies on deep, well-developed techniques with roots in areas such as algebra, probability, or topology. One of the more recent techniques, referred to as the Regularity Method, employs the idea of quasi-randomness. A quasi-random object is one which shares its properties with many other objects of the same kind, thus capturing the idea of a deterministic realization of a "random object." A celebrated result due to Szemeredi, known as the Regularity Lemma, asserts that every graph can be decomposed into relatively few subgraphs that are "typical," or quasi-random. This quasi-randomness enables one to find and enumerate subgraphs of a given isomorphism type, leading to many applications. In this talk, I will illustrate the Regularity Method on problems with connections to combinatorial geometry, extremal combinatorics and number theory. I will also discuss recent work leading to the extensions of the Regularity Method to hypergraphs.