Abstract
The celebrated triangle removal lemma for graphs (Ruzsa-Szemeredi) has important applications in extremal graph theory and additive/combinatorial number theory (e.g., it implies Roth's theorem on sets of integers with no 3 term arithmetic progression). It can be interpreted as stating that in a certain hypergraph any set that spans few edges can be made independent by removing few vertices.
We prove a similar statement "one level down," in (certain) graphs, e.g. Kneser graphs and certain product graphs. As a corollary we strengthen the characterization of intersecting families of sets given by Dinur and Friedgut, and the characterization of independent sets in product graphs by Dinur Friedgut and Regev.
The techniques we use build on the aforementioned result of DFR (that uses the famous MOO (Mossel, O'Donnell, Oleszkiewicz) invariance principle as an engine), and also follow Fox's relatively new proof of the triangle removal lemma.
Joint work with Oded Regev.