abstract

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.