Combinatorics Seminar
When: Sunday, November 19, 10am
Where: Schreiber 309
Speaker: Shachar Sapir, Tel Aviv University
Title: The Induced Graph Removal Lemma in Sparse Graphs
Abstract:
The induced removal lemma of Alon, Fischer, Krivelevich and Szegedy states
that if an n-vertex graph G is ε-far from being induced H-free then G
contains c⋅nh induced copies of H for some c=c(ε). Improving upon
the original proof, Conlon and Fox proved that 1/c is at most a tower
of height poly(1/ε), and asked if this bound can be further improved to
a tower of height log(1/ε). We will show how to obtain such a bound for
graphs G of density O(ε). We will actually prove a more general result,
which, as a special case, also gives a new proof of Fox's upper bound for
the (non-induced) removal lemma.
In the second part of the talk, if time allows, we will discuss the
relation between being far from (induced) H-freeness, and having many
pairwise-disjoint (induced) copies of H. We will show that in the induced
case, this relation can't give us the same bounds as in the non-induced
case, regarding the number of pairwise-disjoint induced copies of H.
Joint work with A. Shapira.