Skip to main content

Applications of the Regularity Lemma

The Regularity Lemma turned out to be one of the most powerful tools in solving Ramsey type, covering, and partitioning problems in graph and hypergraph theory. Recent results of the team lead by V. Rödl shows that finally a very useful (but complicated) hypergraph version of the Regularity Lemma is also obtained. In the last year we already managed to solve a couple of longstandig open problems using the Regularity Lemma-Blow-up Lemma method. For example we determined the exact value of the Ramsey numbers of paths in case of three colors, which solved a conjecture of Faudree and Schelp. During this project we continue this line of investigations and hopefully we will be able to utilize the power of the hypergraph version of the Regularity Lemma.

Participating institutes:

  • MTA SZTAKI (Discrete Structures Group)
  • Rutgers University
  • Rényi Institute
  • University of Memphis