The Minimum Degree Removal Lemma Thresholds

EUROCOMB’23

Abstract
The graph removal lemma is a fundamental result in extremal graph theory which says that for every fixed graph $H$ and $\varepsilon > 0$, if an $n$-vertex graph $G$ contains $\varepsilon n^2$ edge-disjoint copies of $H$ then $G$ contains $\delta n^{v(H)}$ copies of $H$ for some $\delta = \delta(\varepsilon,H) > 0$. The current proofs of the removal lemma give only very weak bounds on $\delta(\varepsilon,H)$, and it is also known that $\delta(\varepsilon,H)$ is not polynomial in $\varepsilon$ unless $H$ is bipartite. Recently, Fox and Wigderson initiated the study of minimum degree conditions guaranteeing that $\delta(\varepsilon,H)$ depends polynomially or linearly on $\varepsilon$. We answer several questions of Fox and Wigderson on this topic.

Pages:
485–490
References

Allen, P., Böttcher, J., Griffiths, S., Kohayakawa, Y., & Morris, R. (2013). The chromatic thresholds of graphs. Advances in Mathematics, 235, 261-295.
https://doi.org/10.1016/j.aim.2012.11.016

Alon, N. (2002). Testing subgraphs in large graphs. Random Structures & Algorithms, 21(3-4), 359-370.
https://doi.org/10.1002/rsa.10056

Alon, N., & Spencer, J. (2016). The probabilistic method. John Wiley & Sons.

Andrásfai, B., Erdős, P., & Sos, V. (1974). On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Mathematics, 8(3), 205-218.
https://doi.org/10.1016/0012-365X(74)90133-2

Brandt, S. (1999). On the structure of dense triangle-free graphs. Combinatorics, Probability and Computing, 8(3), 237-245.
https://doi.org/10.1017/S0963548399003831

Brandt, S., & Thomassé, S. (2011). Dense triangle-free graphs are four-colorable: A solution to the Erdős-Simonovits problem. preprint.

Chen, C.C., Jin, G., & Koh, K. (1997). Triangle-free graphs with large degree. Combinatorics, Probability and Computing, 6(4), 381-396.
https://doi.org/10.1017/S0963548397003167

Ebsen, O., & Schacht, M. (2020). Homomorphism thresholds for odd cycles. Combinatorica, 40(1), 39-62.
https://doi.org/10.1007/s00493-019-3920-8

Erdős, P. (1964). On extremal problems of graphs and generalized graphs. Israel Journal of Mathematics, 2(3), 183-190.
https://doi.org/10.1007/BF02759942

Erdős, P., & Simonovits, M. (1973). On a valence problem in extremal graph theory. Discrete Mathematics, 5(4), 323-334.
https://doi.org/10.1016/0012-365X(73)90126-X

Fox, J. (2011). A new proof of the graph removal lemma. Annals of Mathematics, 561-579.
https://doi.org/10.4007/annals.2011.174.1.17

Fox, J., & Wigderson, Y. (2021). Minimum degree and the graph removal lemma. Journal of Graph Theory.
https://doi.org/10.1002/jgt.22891

Goddard, W., & Lyle, J. (2011). Dense graphs with small clique number. Journal of Graph Theory, 66(4), 319-331.
https://doi.org/10.1002/jgt.20505

Häggkvist, R. (1982). Odd cycles of specified length in non-bipartite graphs. In North-
https://doi.org/10.1016/S0304-0208(08)73552-7

Holland Mathematics Studies, volume 62, 89-99. Elsevier.

Jin, G. (1995). Triangle-free four-chromatic graphs. Discrete Mathematics, 145(1-3), 151-170.
https://doi.org/10.1016/0012-365X(94)00063-O

Letzter, S., & Snyder, R. (2019). The homomorphism threshold of {C3,C5}-free graphs. Journal of Graph Theory, 90(1), 83-106.
https://doi.org/10.1002/jgt.22369

Luczak, T. (2006). On the structure of triangle-free graphs of large minimum degree. Combinatorica, 26(4), 489-493.
https://doi.org/10.1007/s00493-006-0028-8

Luczak, T., & Thomassé, S. (2010). Coloring dense graphs via VC-dimension. arXiv preprint arXiv:1007.1670.

Lyle, J. (2011). On the chromatic number of H-free graphs of large minimum degree. Graphs and Combinatorics, 27(5), 741-754.
https://doi.org/10.1007/s00373-010-0994-x

Nakar, Y., & Ron, D. (2018). On the testability of graph partition properties. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018).

Oberkampf, H., & Schacht, M. (2020). On the structure of Dense graphs with bounded clique number. Combinatorics, Probability and Computing, 29(5), 641-649.
https://doi.org/10.1017/S0963548319000324

Ruzsa, I. Z., & Szemerédi, E. (1978). 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,, volume 18, pages 939-945. North-Holland, Amsterdam-New York.

Sankar, M. (2022). Homotopy and the Homomorphism Threshold of Odd Cycles. arXiv preprint arXiv:2206.07525.

Thomassen, C. (2002). On the chromatic number of triangle-free graphs of large minimum degree. Combinatorica, 22(4), 591-596.
https://doi.org/10.1007/s00493-002-0009-5

Thomassen, C. (2007). On the chromatic number of pentagon-free graphs of large minimum degree. Combinatorica, 27(2), 241-243.
https://doi.org/10.1007/s00493-007-0054-1

Metrics

0

Views

0

PDF views