Arithmetic and Algebraic Regularity Lemmas<br/><br/>Introduced by: Joel Spencer
Saturday, December 1, 2012 - 10:30am - 11:30am
Szemeredi's regularity lemma is a basic structural result that gives a useful description of arbitrary large dense graphs, of importance in graph theory and theoretical computer science. There are now many variants of this lemma that apply to other graph or graph-like models. In this talk we discuss two of these. The first is the arithmetic regularity lemma that gives a useful description of the arithmetic structure of large dense subsets of an finite abelian group; this was first worked out for Green in the case of complexity 1 arithmetic structure, and then by Green and myself to handle arithmetic structure of arbitrary finite complexity. This can be used to answer a number of questions in additive combinatorics (for instance, it gives yet another proof of Szemeredi's theorem on arithmetic progressions). The second (and more recent) is an algebraic regularity lemma that gives a structural description of graphs that are definable over finite fields, using the algebraic structure to give significantly stronger structural control than what one can obtain just from the Szemeredi regularity lemma. As an application, we are able to classify the polynomials P: F x F -> F over a finite field F of large characteristic which are expanding in the sense that P(A,B) has positive density whenever A,B are reasonably large subsets of F.