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.