Applications of the Removal Lemma

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Applications of the Removal Lemma
Speaker:Jozsef Solymosi
Affiliation:University of British Columbia and Member, School of Mathematics
Date:Tuesday, November 13
Time/Room:10:30am - 12:30pm/S-101

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.