An efficient asymmetric removal lemma and its limitations

Gishboliner, Lior  ; Shapira, Asaf  ; Wigderson, Yuval 

Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e38

Résumé

The triangle removal states that if G contains $\varepsilon n^2$ edge-disjoint triangles, then G contains $\delta (\varepsilon )n^3$ triangles. Unfortunately, there are no sensible bounds on the order of growth of $\delta (\varepsilon )$, and at any rate, it is known that $\delta (\varepsilon )$ is not polynomial in $\varepsilon $. Csaba recently obtained an asymmetric variant of the triangle removal, stating that if G contains $\varepsilon n^2$ edge-disjoint triangles, then G contains $2^{-\operatorname {\mathrm {poly}}(1/\varepsilon )}\cdot n^5$ copies of $C_5$. To this end, he devised a new variant of Szemerédi’s regularity lemma. We obtain the following results: • We first give a regularity-free proof of Csaba’s theorem, which improves the number of copies of $C_5$ to the optimal number $\operatorname {\mathrm {poly}}(\varepsilon )\cdot n^5$.• We say that H is $K_3$-abundant if every graph containing $\varepsilon n^2$ edge-disjoint triangles has $\operatorname {\mathrm {poly}}(\varepsilon )\cdot n^{\lvert V(H)\rvert }$ copies of H. It is easy to see that a $K_3$-abundant graph must be triangle-free and tripartite. Given our first result, it is natural to ask if all triangle-free tripartite graphs are $K_3$-abundant. Our second result is that assuming a well-known conjecture of Ruzsa in additive number theory, the answer to this question is negative.Our proofs use a mix of combinatorial, number-theoretic, probabilistic and Ramsey-type arguments.

Détail

DOI : 10.1017/fms.2024.68

Bibliographie

[1] Alon, N., ‘Explicit Ramsey graphs and orthonormal labelings’, Electron. J. Combin. 1 (1994), Research Paper 12, 8 pp. Google Scholar | DOI

[2] Alon, N., ‘Testing subgraphs in large graphs’, Random Structures Algorithms 21 (2002), 359–370. Google Scholar | DOI

[3] Alon, N. and Krivelevich, M., ‘Testing -colorability’, SIAM J. Discrete Math. 15 (2002), 211–227. Google Scholar | DOI

[4] Alon, N. and Shapira, A., ‘A characterization of easily testable induced subgraphs’, Combin. Probab. Comput. 15 (2006), 791–805. Google Scholar | DOI

[5] Behrend, F. A., ‘On sets of integers which contain no three terms in arithmetical progression’, Proc. Nat. Acad. Sci. U.S.A. 32 (1946), 331–332. Google Scholar PubMed | DOI

[6] Bollobás, P. Erdős, M. Simonovits, and Szemerédi, E., ‘Extremal graphs without large forbidden subgraphs’, Ann. Discrete Math. 3 (1978), 29–41. Google Scholar | DOI

[7] Conlon, D. and Fox, J., ‘Graph removal lemmas’, in Surveys in Combinatorics 2013 (London Math. Soc. Lecture Note Ser.) vol. 409 (Cambridge Univ. Press, Cambridge, 2013), 1–49. Google Scholar

[8] Conlon, D., Fox, J., Sudakov, B. and Zhao, Y., ‘The regularity method for graphs with few 4-cycles’, J. Lond. Math. Soc. (2) 104 (2021), 2376–2401. Google Scholar | DOI

[9] Csaba, B., ‘Regular decomposition of the edge set of graphs with applications’, Preprint, 2021, . Google Scholar | arXiv

[10] Duke, R. A., Lefmann, H. and Rödl, V., ‘A fast approximation algorithm for computing the frequencies of subgraphs in a given graph’, SIAM J. Comput. 24 (1995), 598–620. Google Scholar | DOI

[11] Erdős, P., ‘On extremal problems of graphs and generalized graphs’, Israel J. Math. 2 (1964), 183–190. Google Scholar | DOI

[12] Fox, J., ‘A new proof of the graph removal lemma’, Ann. of Math. (2) 174 (2011), 561–579. Google Scholar | DOI

[13] Fox, J. and Zhao, Y., ‘Removal lemmas and approximate homomorphisms’, Combin. Probab. Comput. 31 (2022), 721–736. Google Scholar | DOI

[14] Frieze, A. and Kannan, R., ‘Quick approximation to matrices and applications’, Combinatorica 19 (1999), 175–220. Google Scholar | DOI

[15] Gishboliner, L. and Shapira, A., ‘A generalized Turán problem and its applications’, Int. Math. Res. Not. IMRN (2020), 3417–3452. Google Scholar | DOI

[16] Goldreich, O., Goldwasser, S. and Ron, D., ‘Property testing and its connection to learning and approximation’, J. ACM 45 (1998), 653–750. Google Scholar | DOI

[17] Komlós, J., ‘Covering odd cycles’, Combinatorica 17 (1997), 393–400. Google Scholar | DOI

[18] Kövari, T., Sós, V. T., and Turán, P., ‘On a problem of K. Zarankiewicz’, Colloq. Math. 3 (1954), 50–57. Google Scholar | DOI

[19] Ruzsa, I. Z., ‘Solving a linear equation in a set of integers. I’, Acta Arith. 65 (1993), 259–282. Google Scholar | DOI

[20] Ruzsa, I. Z. and Szemerédi, E., ‘Triple systems with no six points carrying three triangles’, in Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai vol. 18 (North-Holland, Amsterdam-New York, 1978), 939–945. Google Scholar