Graph Theory and Combinatorics Seminar

Title: Regularity method in sparse setting. 

Abstract: The regularity method is a well known tool in extremal combinatorics which has seen several applications since it was introduced by Szemer\'edi in the 1970s as a tool to prove Szemer\'edi's theorem. A particularly well known consequence of it is the triangle removal lemma which states that if a graph $G$ on $n$ vertices contains $o(n^3)$  triangles, it can be made triangle free by removing $o(n^2)$ edges. 

While in the dense case, such a statement has many applications, in the sparse case,  such statements do not hold in general. A removal lemma was shown to be true for subgraphs of sparse random graphs by Conlon, Gowers, Samotij and Schacht. Subsequently, Conlon, Fox, Sudakov and Zhao also showed a removal lemma (only for particular graphs) in C_4 free graphs, which are also sparse. 

Here we discuss a generalization to sparse 3-uniform hypergraphs. In particular we show a removal lemma in a hypergraph which has no 4-cycle in its link.