HOME    »    SCIENTIFIC RESOURCES    »    Volumes
Abstracts and Talk Materials
3rd Abel Conference: A Mathematical Celebration of Endre Szemeredi
November 29-December 1, 2012

Noga Alon

On Graphs, Progressions and Communication
Introduced by: Zoltan Furedi

November 30, 2012

Keywords of the presentation: Induced matchings, Arithmetic progressions, Communication Complexity

Tools from Extremal Graph Theory are helpful in the study of problems in Additive Number Theory, Theoretical Computer Science, and Information Theory. I will illustrate this fact by several closely related examples focusing on a recent one in a joint work with Moitra and Sudakov.

The main combinatorial question addressed, whose study was initiated by Ruzsa and Szemeredi, is that of estimating the maximum possible density of a graph consisting of a union of pairwise edge disjoint large induced matchings. This is strongly related to questions in additive number theory, theoretical computer science and communication complexity.

Jacob Fox

Szemerédi's Regularity Lemma, Variants, and Applications
Introduced by: Van Vu

November 30, 2012

Keywords of the presentation: regularity lemma, removal lemma, sparse graphs

Szemerédi's regularity lemma is one of the most powerful tools in graph theory, with many applications in combinatorics, number theory, discrete geometry, and theoretical computer science. Roughly speaking, it says that every large graph can be partitioned into a small number of parts such that the bipartite subgraph between almost all pairs of parts is random-like. Several variants of the regularity lemma have since been established yielding many further applications. In this talk, I will survey this area, including recent progress on quantitative estimates in the various regularity lemmas, and alternative methods yielding new proofs of applications with improved quantitative estimates.

Hillel Furstenberg

A Szemeredi--Type Theorem for Non-Amenable Groups
Introduced by: Jeff Kahn

November 29, 2012

Keywords of the presentation: Stationary, Multiple Recurrence, Geometric Progression,Non-amenable

Let G be a group and m a probability measure on G. One can speak of a "stationary" (rather than "invariant") density on G, and for an action of G on a compact space X one can talk of a "stationary" (rather than "invariant") measure on X. One can also establish a "correspondence principle" in this setting, and also prove "multiple recurrence" for stationary actions. These ideas lead to a general Szemeredi-type theorem, which is quite explicit for finitely generated free groups as well as for certain infinite regular graphs.

Bryna Kra

Complexity and Periodicity
Introduced by: Tom Trotter

November 29, 2012

Keywords of the presentation: periodic, complexity, dynamics, Nivat Conjecture

The interaction between combinatorics and dynamics is a classical subject and an illustration of this interaction arises in the combinatorics of words. The Morse-Hedlund Theorem states that an infinite word in a finite alphabet is periodic if and only if there is exists a positive integer n such that the complexity (the number of words of length n) is bounded by n. A natural approach to this theorem is via analyzing the dynamics of the Z-action associated to the word. Periodicity and complexity have natural generalizations to higher dimensions, but there is no simple analog of the Morse-Hedlund Theorem. I will give an overview of results in higher dimensions, including progress on a conjecture of Nivat in 2 dimensions. This is joint work with Van Cyr.

János Pach

The Reluctant Semi-Algebraist
Introduced by: Janos Pintz

December 1, 2012

Keywords of the presentation: Ramsey problem, semi-algebraic set, intersection graph, Szemeredi partition

By Ramsey's theorem, any system of n segments in the plane has roughly logn members that are either pairwise disjoint or pairwise intersecting. Analogously, any set of n points p(1),..., p(n) in the plane has a subset of roughly loglogn elements with the property that the orientation of p(i)p(j)p(k) is the same for all triples from this subset with i less than j less than k. (The elements of such a subset form the vertex set of a convex polygon.) However, in both cases we know that there exist much larger "homogeneous" subsystems satisfying the above conditions. What is behind this favorable behavior? One of the common features of the above problems is that the underlying graphs and triple-systems can be defined by a small number of polynomial equations and inequalities in terms of the coordinates of the segments and points. We discuss some structural properties of "semi-algebraically" defined graphs and hypergraphs, including Szemeredi-type partition theorems. Finally, we mention some joint results with Conlon, Fox, Sudakov, and Suk, establishing new Ramsey-type bounds for such hypergraphs.

Vojtêch Rödl

Graph, Hypergraph, Szemeredi Regularity Lemma
Introduced by: Penny Haxell

November 30, 2012

We will review a few extremal problems that motivated the extensions of Szemeredi's regularity lemma to hypergraphs and sparse graphs. We discuss some of the developments in those areas over the last 10 years.

Vera T. Sos

Szemeredi Regularity Lemma and Limit of Graphs
Introduced by: Miklós Simonovits

November 30, 2012

The Szemeredi regularity lemma is crucial in graph limit theory.It is a basic tool to study large dense graphs: e.g. how to consider similarity, approximation by small graphs, how local and global properties are related to each other. It provides important new bridge between graph theory and other fields like analysis, probability, topology.Focusing on these aspects, I will give a reiew on some parts of limit theory - which developed in the last few years in the center with Laszlo Lovasz.

Balazs Szegedy

Regularity, Factors and Limit Structures
Introduced by: Gyula Katona

November 29, 2012

Keywords of the presentation: regularity lemma; ergodic theory; Gowers norms; limits of structures

Szemeredi's regularity lemma has opened up a new perspective in understanding very large structures. It has numerous applications in combinatorics, computer science and many other areas. A similar story of success is the theory of (characteristic) factors in ergodic theory. In the present talk we show how to look at these subjects from a unified point of view in the frame of which limits of structures are considered.

Terence Tao

Arithmetic and Algebraic Regularity Lemmas
Introduced by: Joel Spencer

December 1, 2012

Keywords of the presentation: regularity lemma, additive combinatorics, definable sets

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.

Avi Wigderson

Points, Lines and Ranks of Design Matrices
Introduced by: Bill Steiger

November 29, 2012

The Sylvester-Gallai theorem in Euclidean geometry asserts that if a set of points has the property that every line through two of them contains a third point (such lines are called "special"), then they must all be on the same line, namely, 1-dimensional. There are many proofs, all elementary. When one moves to the complex numbers the same condition can be met in two dimensions, and Kelly's theorem asserts that the points mus lie in a 2-dimensional space. The first proof used algebraic geometry, and a later more elementary proof of this fact is still quite complicated.

We prove several extensions and quantitative versions of these theorems (and related ones), in which the assumption is relaxed to having "many" special lines in the given point set (but not all), still imply a constant upper bound on the dimension of the point set. We also address "robust" versions in which triples of points are "nearly collinear" - here we infer that all points are "close" to a low dimensional subspace. These relaxations are motivated from questions about locally correctable codes, matrix rigidity, arithmetic combinatorics and more.

Our results are obtained via general, tight rank lower bounds on matrices about with certain zero/non-zero pattern of entries. The proofs use an interesting combination of combinatorial, algebraic and analytic tools. In particular, they supply a simple new proof of Kelly's theorem.

Based on several joint works with Albert Ai, Boaz Barak, Zeev Dvir, Shubhangi Saraf and Amir Yehudayoff.