November 29 - December 1, 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.