A sparse regular approximation lemma
HTML articles powered by AMS MathViewer
- by Guy Moshkovitz and Asaf Shapira PDF
- Trans. Amer. Math. Soc. 371 (2019), 6779-6814 Request permission
Abstract:
We introduce a new variant of Szemerédi’s regularity lemma which we call the sparse regular approximation lemma (SRAL). The input to this lemma is a graph $G$ of edge density $p$ and parameters $\epsilon , \delta$, where we think of $\delta$ as a constant. The goal is to construct an $\epsilon$-regular partition of $G$ while having the freedom to add/remove up to $\delta |E(G)|$ edges. As we show here, this weaker variant of the regularity lemma already suffices for proving the graph removal lemma and the hypergraph regularity lemma, which are two of the main applications of the (standard) regularity lemma. This of course raises the following question: can one obtain quantitative bounds for SRAL that are significantly better than those associated with the regularity lemma?
Our first result answers the above question affirmatively by proving an upper bound for SRAL given by a tower of height $O(\log 1/p)$. This allows us to reprove Fox’s upper bound for the graph removal lemma. Our second result is a matching lower bound for SRAL showing that a tower of height $\Omega (\log 1/p)$ is unavoidable. We in fact prove a more general multicolored lower bound which is essential for proving lower bounds for the hypergraph regularity lemma.
References
- Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), no. 4, 451–476. MR 1804820, DOI 10.1007/s004930070001
- David Conlon and Jacob Fox, Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), no. 5, 1191–1256. MR 2989432, DOI 10.1007/s00039-012-0171-x
- David Conlon and Jacob Fox, Graph removal lemmas, Surveys in combinatorics 2013, London Math. Soc. Lecture Note Ser., vol. 409, Cambridge Univ. Press, Cambridge, 2013, pp. 1–49. MR 3156927
- Richard A. Duke, Hanno Lefmann, and Vojtěch Rödl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph, SIAM J. Comput. 24 (1995), no. 3, 598–620. MR 1333857, DOI 10.1137/S0097539793247634
- Jacob Fox, A new proof of the graph removal lemma, Ann. of Math. (2) 174 (2011), no. 1, 561–579. MR 2811609, DOI 10.4007/annals.2011.174.1.17
- Peter Frankl and Vojtěch Rödl, Extremal problems on set systems, Random Structures Algorithms 20 (2002), no. 2, 131–164. MR 1884430, DOI 10.1002/rsa.10017.abs
- Alan Frieze and Ravi Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, 175–220. MR 1723039, DOI 10.1007/s004930050052
- W. T. Gowers, Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal. 7 (1997), no. 2, 322–337. MR 1445389, DOI 10.1007/PL00001621
- W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. (2) 166 (2007), no. 3, 897–946. MR 2373376, DOI 10.4007/annals.2007.166.897
- Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. MR 144363
- Robert M. Gray, Entropy and information theory, 2nd ed., Springer, New York, 2011. MR 3134681, DOI 10.1007/978-1-4419-7970-4
- J. Komlós and M. Simonovits, Szemerédi’s regularity lemma and its applications in graph theory, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 295–352. MR 1395865
- László Lovász and Balázs Szegedy, Szemerédi’s lemma for the analyst, Geom. Funct. Anal. 17 (2007), no. 1, 252–270. MR 2306658, DOI 10.1007/s00039-007-0599-6
- Guy Moshkovitz and Asaf Shapira, A short proof of Gowers’ lower bound for the regularity lemma, Combinatorica 36 (2016), no. 2, 187–194. MR 3516883, DOI 10.1007/s00493-014-3166-4
- Brendan Nagle, Vojtěch Rödl, and Mathias Schacht, The counting lemma for regular $k$-uniform hypergraphs, Random Structures Algorithms 28 (2006), no. 2, 113–179. MR 2198495, DOI 10.1002/rsa.20117
- M. S. Pinsker, Information and information stability of random variables and processes, Holden-Day, Inc., San Francisco, Calif.-London-Amsterdam, 1964. Translated and edited by Amiel Feinstein. MR 0213190
- Vojtěch Rödl and Mathias Schacht, Regular partitions of hypergraphs: regularity lemmas, Combin. Probab. Comput. 16 (2007), no. 6, 833–885. MR 2351688, DOI 10.1017/s0963548307008553
- Vojtěch Rödl and Mathias Schacht, Regularity lemmas for graphs, Fete of combinatorics and computer science, Bolyai Soc. Math. Stud., vol. 20, János Bolyai Math. Soc., Budapest, 2010, pp. 287–325. MR 2798368, DOI 10.1007/978-3-642-13580-4_{1}1
- Vojtěch Rödl and Jozef Skokan, Regularity lemma for $k$-uniform hypergraphs, Random Structures Algorithms 25 (2004), no. 1, 1–42. MR 2069663, DOI 10.1002/rsa.20017
- Alexander Scott, Szemerédi’s regularity lemma for matrices and sparse graphs, Combin. Probab. Comput. 20 (2011), no. 3, 455–466. MR 2784637, DOI 10.1017/S0963548310000490
- I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 939–945. MR 519318
- Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
- Terence Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), no. 7, 1257–1280. MR 2259060, DOI 10.1016/j.jcta.2005.11.006
- Terence Tao, Szemerédi’s regularity lemma revisited, Contrib. Discrete Math. 1 (2006), no. 1, 8–28. MR 2212136
Additional Information
- Guy Moshkovitz
- Affiliation: School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel
- MR Author ID: 1024052
- Email: guymosko@tau.ac.il
- Asaf Shapira
- Affiliation: School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel
- MR Author ID: 715511
- Email: asafico@tau.ac.il
- Received by editor(s): November 3, 2016
- Received by editor(s) in revised form: August 28, 2017
- Published electronically: February 22, 2019
- Additional Notes: The second author was supported in part by ISF Grant 1028/16 and ERC-Starting Grant 633509.
- © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 371 (2019), 6779-6814
- MSC (2010): Primary 05C35, 05D99
- DOI: https://doi.org/10.1090/tran/7414
- MathSciNet review: 3939561