Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-30T23:24:49.472Z Has data issue: false hasContentIssue false
  • English
  • Français

The Induced Removal Lemma in Sparse Graphs

Part of: Extremal combinatorics

Published online by Cambridge University Press:  30 September 2019

Shachar Sapir  and
Asaf Shapira
Shachar Sapir
Affiliation:
School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel
Asaf Shapira*
Affiliation:
School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 δH(ε) · nh induced copies of H. Improving upon the original proof, Conlon and Fox proved that 1/δH(ε)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/ε). In this paper we obtain such a bound for graphs G of density O(ε). We actually prove a more general result, which, as a special case, also gives a new proof of Fox’s bound for the (non-induced) removal lemma.

MSC classification

Primary: 05D99: None of the above, but in this section
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 1 , January 2020 , pp. 153 - 162
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Supported in part by ISF Grant 1028/16 and ERC Starting Grant 633509.

References

Alon, N., Duke, R. A., Lefmann, H., Rödl, V. and Yuster, R. (1994) The algorithmic aspects of the regularity lemma. J. Algorithms 16 80–109.CrossRefGoogle Scholar
Alon, N., Fischer, E., Krivelevich, M. and Szegedy, M. (2000) Efficient testing of large graphs. Combinatorica 20 451–476.CrossRefGoogle Scholar
Conlon, D. and Fox, J. (2012) Bounds for graph regularity and removal lemmas. Geom. Funct. Anal. 22 1191–1256.CrossRefGoogle Scholar
Conlon, D. and Fox, J. (2013) Graph removal lemmas. In Surveys in Combinatorics 2013, Vol. 409 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 1–50.Google Scholar
Duke, R., Lefmann, H. and Rödl, V. (1995) A fast approximation algorithm for computing the frequencies of subgraphs in a given graph. SIAM J. Comput. 24 598–620.CrossRefGoogle Scholar
Erdös, P., Frankl, P. and Rödl, V. (1986) The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin. 2 113–121.CrossRefGoogle Scholar
Fox, J. (2011) A new proof of the graph removal lemma. Ann. of Math. 174 561–579.CrossRefGoogle Scholar
Gowers, W. T. (1997) Lower bounds of tower type for Szemerédi’s uniformity lemma. Geom. Funct. Anal. 7 322–337.CrossRefGoogle Scholar
Moshkovitz, G. and Shapira, A. (2019) A sparse regular approximation lemma. Trans. Amer. Math. Soc. 371 6779–6814.CrossRefGoogle Scholar
Ruzsa, I. Z. and Szemerédi, E. (1978) Triple systems with no six points carrying three triangles. In Combinatorics (Keszthely, 1976), Vol. II, Vol. 18 of Colloquia Mathematica Societatis János Bolyai, pp. 939–945.Google Scholar
Szemerédi, E. (1978) Regular partitions of graphs. In Proc. Colloque Inter. CNRS, pp. 399–401.Google Scholar