Resolution of the Erdős–Sauer problem on regular subgraphs

Oliver Janzer ; Benny Sudakov

Forum of Mathematics, Pi, Tome 11 (2023)

Résumé

In this paper, we completely resolve the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an n-vertex graph can have without containing a k-regular subgraph, for some fixed integer $k\geq 3$. We prove that any n-vertex graph with average degree at least $C_k\log \log n$ contains a k-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough.Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.

Détail

DOI : 10.1017/fmp.2023.19

Bibliographie

[1] Alon, N., ‘Problems and results in extremal combinatorics—II’, Discrete Mathematics 308(19) (2008), 4460–4472, 2008.Google Scholar | DOI

[2] Alon, N., ‘A note on degenerate and spectrally degenerate graphs’, Journal of Graph Theory 72(1) (2013), 1–6, 2013.Google Scholar | DOI

[3] Alon, N., Cohen, J. D., Dey, B., Griffiths, T., Musslick, S., Ozcimder, K., Reichman, D., Shinkar, I. and Wagner, T., ‘A graph-theoretic approach to multitasking’, Preprint, 2016, .Google Scholar | arXiv

[4] Alon, N., Friedland, S. and Kalai, G., ‘Every 4-regular graph plus an edge contains a 3-regular subgraph’, Journal of Combinatorial Theory, Series B 37 (1984), 92–93.Google Scholar | DOI

[5] Alon, N., Friedland, S. and Kalai, G., ‘Regular subgraphs of almost regular graphs’, Journal of Combinatorial Theory, Series B 37(1) (1984), 79–91.Google Scholar | DOI

[6] Alon, N., Reichman, D., Shinkar, I., Wagner, T., Musslick, S., Cohen, J. D., Griffiths, T., Dey, B. and Ozcimder, K., ‘A graph-theoretic approach to multitasking’, Advances in Neural Information Processing Systems 30 (2017).Google Scholar

[7] Bollobás, B., Extremal Graph Theory (Academic Press, 1978).Google Scholar

[8] Bollobás, B., Kim, J. H. and Verstraëte, J., ‘Regular subgraphs of random graphs’, Random Structures & Algorithms 29(1) (2006), 1–13.Google Scholar | DOI

[9] Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications, vol. 290 (Macmillan, London, 1976).Google Scholar | DOI

[10] Bucić, M., Kwan, M., Pokrovskiy, A., Sudakov, B., Tran, T. and Wagner, A. Z., ‘Nearly-linear monotone paths in edge-ordered graphs’, Israel Journal of Mathematics 238(2) (2020), 663–685.Google Scholar | DOI

[11] Dellamonica, D., Haxell, P., Łuczak, T., Mubayi, D., Nagle, B., Person, Y., Rödl, V., Schacht, M. and Verstraëte, J., ‘On even-degree subgraphs of linear hypergraphs’, Combinatorics, Probability and Computing 21(1–2) (2012), 113–127.Google Scholar | DOI

[12] Dellamonica, D. Jr and Rödl, V., ‘A note on Thomassen’s conjecture’, Journal of Combinatorial Theory, Series B 101(6) (2011), 509–515.Google Scholar | DOI

[13] Dvořák, Z. and Mohar, B., ‘Spectrally degenerate graphs: Hereditary case’, Journal of Combinatorial Theory, Series B 102(5) (2012), 1099–1109.Google Scholar | DOI

[14] Erdős, P., ‘Some recent progress on extremal problems in graph theory’, Congr. Numer. 14 (1975), 3–14.Google Scholar

[15] Erdős, P. and Simonovits, M., ‘Some extremal problems in graph theory’, in Combinatorial Theory and Its Applications, I (North Holland, Amsterdam, 1970), 377–390.Google Scholar

[16] Erdős, P., ‘On the combinatorial problems which I would most like to see solved’, Combinatorica 1(1) (1981), 25–42.Google Scholar | DOI

[17] Hall, P., ‘On representatives of subsets’, J. London Math. Soc. 10 (1935), 26–30.Google Scholar | DOI

[18] Han, J. and Kim, J., ‘Two-regular subgraphs of odd-uniform hypergraphs’, Journal of Combinatorial Theory, Series B 128 (2018), 175–191.Google Scholar | DOI

[19] Kim, J., ‘Regular subgraphs of uniform hypergraphs’, Journal of Combinatorial Theory, Series B 119 (2016), 214–236.Google Scholar | DOI

[20] Kim, J. and Kostochka, A. V., ‘Maximum hypergraphs without regular subgraphs’, Discuss. Math. Graph Theory 34(1) (2014), 151–166.Google Scholar | DOI

[21] Kühn, D. and Osthus, D., ‘Every graph of sufficiently large average degree contains a -free subgraph of large average degree’, Combinatorica 24(1) (2004), 155–162.Google Scholar | DOI

[22] Montgomery, R., Pokrovskiy, A. and Sudakov, B., ‘-free subgraphs with large average degree’, Israel Journal of Mathematics 246(1) (2021), 55–71.Google Scholar | DOI

[23] Mubayi, D. and Verstraëte, J., ‘Two-regular subgraphs of hypergraphs’, Journal of Combinatorial Theory, Series B 99(3) (2009), 643–655.Google Scholar | DOI

[24] Petersen, J., ‘Die theorie der regulären graphs’, Acta Mathematica 15(1) (1891), 193–220.Google Scholar | DOI

[25] Pyber, L., ‘Regular subgraphs of dense graphs’, Combinatorica 5(4) (1985), 347–349.Google Scholar | DOI

[26] Pyber, L., Rödl, V. and Szemerédi, E., ‘Dense graphs without 3-regular subgraphs. Journal of Combinatorial Theory, Series B 63(1) (1995), 41–54.Google Scholar | DOI

[27] Rödl, V. and Wysocka, B., ‘Note on regular subgraphs’, Journal of Graph Theory 24(2) (1997), 139–154.Google Scholar | DOI

[28] Thomassen, C., ‘Girth in graphs’, Journal of Combinatorial Theory, Series B 35(2) (1983), 129–141.Google Scholar | DOI

[29] Tutte, W. T., ‘The factorization of linear graphs’, Journal of the London Mathematical Society 1(2) (1947), 107–111.Google Scholar | DOI

[30] Tutte, W. T., ‘The factors of graphs’, Canadian Journal of Mathematics 4 (1952), 314–328.Google Scholar | DOI