Ramsey theory and hypergraph regularity


Szemerédi s celebrated theorem, that states that a set of integers with positive upper density must contain arbitrarily long arithmetic progressions, is considered to be a central theorem in Ramsey theory.



In Szemerédi s original proof a key tool was the regularity lemma that eventually became one of the most important tools in graph theory. In recent proofs by Gowers and, independently, Rödl and others generalizations of the regularity lemma to hypergraphs has been implemented, and these generalizations have the potential to become indispensable tools in the study of hypergraphs.
We wish to investigate several directions, and we represent each by one or two sample problems;


1) We wish to use hypergraph regularity in order prove the density version of some of the central theorems in Ramsey theory: the Hales Jewett theorem for which currently the only known proof is the ergodic theoretic proof of Katznelson and Furstenberg, and Kriz s theorem for which the density version is currently open.


2) We would like to prove the existence of a sharp threshold for some Ramsey properties of random sets of integers, specifically we ask for what values of p does a random subset of the integers {1,2, ,n} with density p have, with high probability, the property that in every two-coloring of it one can find an arithmetic progression of length three? We have good reason to believe that the critical value of p is strongly concentrated around (c/ n) for some constant c, and that a proof of that would involve using hypergraph regularity.


3) An important tool in application of Szemerédi s regularity theorem is the Blowup lemma. We would like to develop the analogous tool for the hypergraph regularity theorems.


Principal investigators
Schacht, Mathias Prof. Ph. D. (Details) (Algorithms and Complexity I)

Financer
German Israel Foundation

Duration of project
Start date: 01/2007
End date: 12/2009

Last updated on 2022-07-09 at 21:06