×

A new proof of the graph removal lemma. (English) Zbl 1231.05133

Summary: Let \(H\) be a fixed graph with \(h\) vertices. The graph removal lemma states that every graph on \(n\) vertices with \(o(n^h)\) copies of \(H\) can be made \(H\)-free by removing \(o(n^2)\) edges. We give a new proof which avoids Szemerédi’s regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.

MSC:

05C35 Extremal problems in graph theory
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Ajtai and E. Szemerédi, ”Sets of lattice points that form no squares,” Stud. Sci. Math. Hungar., vol. 9, pp. 9-11 (1975), 1974. · Zbl 0303.10046
[2] N. Alon, ”Testing subgraphs in large graphs,” Random Structures Algorithms, vol. 21, iss. 3-4, pp. 359-370, 2002. · Zbl 1027.68095 · doi:10.1002/rsa.10056
[3] N. Alon and A. Shapira, ”Testing subgraphs in directed graphs,” J. Comput. System Sci., vol. 69, iss. 3, pp. 353-382, 2004. · Zbl 1084.68087 · doi:10.1016/j.jcss.2004.04.008
[4] N. Alon and J. H. Spencer, The Probabilistic Method, Third ed., Hoboken, NJ: John Wiley & Sons, 2008. · Zbl 1158.60303 · doi:10.1007/978-3-540-85221-6_18
[5] F. A. Behrend, ”On sets of integers which contain no three terms in arithmetical progression,” Proc. Nat. Acad. Sci. U. S. A., vol. 32, pp. 331-332, 1946. · Zbl 0060.10302 · doi:10.1073/pnas.32.12.331
[6] W. G. Brown, P. ErdHos, and V. T. Sós, ”Some extremal problems on \(r\)-graphs,” in New Directions in the Theory of Graphs, New York, 1973, pp. 53-63. · Zbl 0258.05132
[7] S. A. Burr, P. ErdHos, R. L. Graham, and V. T. Sós, ”Maximal anti-Ramsey graphs and the strong chromatic number,” J. Graph Theory, vol. 13, iss. 3, pp. 263-282, 1989. · Zbl 0682.05046 · doi:10.1002/jgt.3190130302
[8] P. ErdHos, ”Problems and results in combinatorial analysis and graph theory,” in Proceedings of the First Japan Conference on Graph Theory and Applications, 1988, pp. 81-92. · Zbl 0661.05037 · doi:10.1016/0012-365X(88)90196-3
[9] P. ErdHos, P. Frankl, and V. Rödl, ”The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent,” Graphs Combin., vol. 2, iss. 2, pp. 113-121, 1986. · Zbl 0593.05038 · doi:10.1007/BF01788085
[10] P. ErdHos and M. Simonovits, ”Supersaturated graphs and hypergraphs,” Combinatorica, vol. 3, iss. 2, pp. 181-192, 1983. · Zbl 0529.05027 · doi:10.1007/BF02579292
[11] O. Goldreich, S. Goldwasser, and D. Ron, ”Property testing and its connection to learning and approximation,” J. ACM, vol. 45, iss. 4, pp. 653-750, 1998. · Zbl 1065.68575 · doi:10.1145/285055.285060
[12] W. T. Gowers, ”Lower bounds of tower type for Szemerédi’s uniformity lemma,” Geom. Funct. Anal., vol. 7, iss. 2, pp. 322-337, 1997. · Zbl 0876.05053 · doi:10.1007/PL00001621
[13] W. T. Gowers, Some unsolved problems in additive/combinatorial number theory.
[14] W. T. Gowers, ”Rough structure and classification,” in GAFA 2000. Visions in Mathematics - Towards 2000, 2000, pp. 79-117. · Zbl 0989.01020
[15] W. T. Gowers, ”A new proof of Szemerédi’s theorem,” Geom. Funct. Anal., vol. 11, iss. 3, pp. 465-588, 2001. · Zbl 1028.11005 · doi:10.1007/s00039-001-0332-9
[16] W. T. Gowers, ”Quasirandomness, counting and regularity for 3-uniform hypergraphs,” Combin. Probab. Comput., vol. 15, iss. 1-2, pp. 143-184, 2006. · Zbl 1082.05081 · doi:10.1017/S0963548305007236
[17] W. T. Gowers, ”Hypergraph regularity and the multidimensional Szemerédi theorem,” Ann. of Math., vol. 166, iss. 3, pp. 897-946, 2007. · Zbl 1159.05052 · doi:10.4007/annals.2007.166.897
[18] B. Green, ”A Szemerédi-type regularity lemma in abelian groups, with applications,” Geom. Funct. Anal., vol. 15, iss. 2, pp. 340-376, 2005. · Zbl 1160.11314 · doi:10.1007/s00039-005-0509-8
[19] J. Komlós and M. Simonovits, ”Szemerédi’s regularity lemma and its applications in graph theory,” in Combinatorics, Paul Erd\Hos is Eighty, Budapest, 1996, pp. 295-352. · Zbl 0851.05065
[20] D. Král, O. Serra, and L. Vena, ”A combinatorial proof of the removal lemma for groups,” J. Combin. Theory Ser. A, vol. 116, iss. 4, pp. 971-978, 2009. · Zbl 1209.05261 · doi:10.1016/j.jcta.2008.12.003
[21] D. Král, O. Serra, and L. Vena, A removal lemma for systems of linear equations over finite fields. · Zbl 1306.11012
[22] B. Nagle, V. Rödl, and M. Schacht, ”The counting lemma for regular \(k\)-uniform hypergraphs,” Random Structures Algorithms, vol. 28, iss. 2, pp. 113-179, 2006. · Zbl 1093.05045 · doi:10.1002/rsa.20117
[23] V. Rödl and J. Skokan, ”Regularity lemma for \(k\)-uniform hypergraphs,” Random Structures Algorithms, vol. 25, iss. 1, pp. 1-42, 2004. · Zbl 1046.05042 · doi:10.1002/rsa.20017
[24] K. F. Roth, ”On certain sets of integers,” J. London Math. Soc., vol. 28, pp. 104-109, 1953. · Zbl 0050.04002 · doi:10.1112/jlms/s1-28.1.104
[25] R. Rubinfeld and M. Sudan, ”Robust characterizations of polynomials with applications to program testing,” SIAM J. Comput., vol. 25, iss. 2, pp. 252-271, 1996. · Zbl 0844.68062 · doi:10.1137/S0097539793255151
[26] I. Z. Ruzsa and E. Szemerédi, ”Triple systems with no six points carrying three triangles,” in Combinatorics, Vol. II, Amsterdam, 1978, pp. 939-945. · Zbl 0393.05031
[27] A. Shapira, ”A proof of Green’s conjecture regarding the removal properties of sets of linear equations,” J. Lond. Math. Soc., vol. 81, iss. 2, pp. 355-373, 2010. · Zbl 1218.05071 · doi:10.1112/jlms/jdp076
[28] I. D. Shkredov, ”On a generalization of Szemerédi’s theorem,” Proc. London Math. Soc., vol. 93, iss. 3, pp. 723-760, 2006. · Zbl 1194.11024 · doi:10.1017/S0024611506015991
[29] J. Solymosi, ”Note on a generalization of Roth’s theorem,” in Discrete and Computational Geometry, New York: Springer-Verlag, 2003, vol. 25, pp. 825-827. · Zbl 1047.52011 · doi:10.1007/s00454-003-0014-7
[30] E. Szemerédi, ”On sets of integers containing no \(k\) elements in arithmetic progression, Collection of articles in memory of JuriĭVladimirovi\vc Linnik,” Acta Arith., vol. 27, pp. 199-245, 1975. · Zbl 0303.10056
[31] E. Szemerédi, ”Regular partitions of graphs,” in Problèmes Combinatoires et Théorie des Graphes, Paris, 1978, pp. 399-401. · Zbl 0413.05055
[32] T. Tao, ”A variant of the hypergraph removal lemma,” J. Combin. Theory Ser. A, vol. 113, iss. 7, pp. 1257-1280, 2006. · Zbl 1105.05052 · doi:10.1016/j.jcta.2005.11.006
[33] T. Tao, Structure and Randomness: Pages from Year One of a Mathematical Blog, Providence, RI: Amer. Math. Soc., 2008. · Zbl 1245.00024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.