Hypergraph regularity and its applications

Abstract:

Szemerédi's Regularity Lemma proved to be a very powerful tool in graph theory with a large number of applications. Therefore, a natural question arises whether it can be generalized to k-uniform hypergraphs. Unlike for graphs, there are several natural ways to define "regularity" (quasi-randomness) for k-uniform hypergraphs. Consequently, various forms of a regularity lemma for hypergraphs have been considered.

One of the main reasons for wide applicability of Szemerédi's Regularity Lemma is the fact that it enables to find all small graphs as subgraphs of a regular graph. P. Frankl and V. Rödl addressed this issue for 3-uniform hypergraphs. Their regularity lemma produces a quasi-random setup in which one can find small subhypergraphs. Recently, V. Rödl and J. Skokan considered the generalization of this lemma to k-uniform hypergraphs for k > 3.

In this talk, we outline the major similarities as well as differences between concepts and results in the graph case and k-uniform hypergraph case. If time permits, we also discuss what kind of applications one can expect from this hypergraph regularity lemma and possible directions for the future research.

This is a joint work with V. Rödl.