Computer Science/Discrete Mathematics Seminar II

An extension of Szemeredi's Regularity Lemma for hypergraphs, was proved in 2005 by Gowers and independently by Rodl, Schacht, Skokan, and Nagle. More recently, Tao gave another proof for the lemma. A special case, the Removal Lemma is an important corollary of the Hypergraph Regularity Lemma. The following statement follows from the Removal Lemma: For any c > 0 real and k > 1 integer, there is a c' > 0, such that if a k-uniform hypergraph on n vertices contains at least cn^k pairwise edge-disjoint cliques then it contains many, at least c'n^{k+1}, cliques. The Removal Lemma is a powerful tool. In this talk we will review a few applications of the lemma. In particular we shall see that the statement above implies the multidimensional Szemeredi Theorem.