Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-08T02:10:43.067Z 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: asafico@tau.ac.il
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 1 , January 2020 , pp. 153 - 162
Copyright
© Cambridge University Press 2019 

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