Friday, March 7, 2003
11:30 am, Science Building, 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.