Induced graph removal

Induced graph removal

Tue, 11/10/2011
14:30 		David Conlon (Oxford) Combinatorial Theory Seminar Add to calendar L3
Induced graph removal
The induced graph removal lemma states that for any fixed graph $ H $ on $ h $ vertices and any $ e\textgreater 0 $ there exists $ d\textgreater0 $ such that any graph $ G $ with at most $ d n^h $ induced copies of $ H $ may be made $ H $-free by adding or removing atmost $ e n^2 $ edges. This fact was originally proven by Alon, Fischer, Krivelevich and Szegedy. In this talk, we discuss a new proof and itsrelation to various regularity lemmas. This is joint work with Jacob Fox.