A solution to Erdős and Hajnal’s odd cycle problem
HTML articles powered by AMS MathViewer
- by Hong Liu and Richard Montgomery
- J. Amer. Math. Soc. 36 (2023), 1191-1234
- DOI: https://doi.org/10.1090/jams/1018
- Published electronically: March 31, 2023
- HTML | PDF
Abstract:
In 1981, Erdős and Hajnal asked whether the sum of the reciprocals of the odd cycle lengths in a graph with infinite chromatic number is necessarily infinite. Let $\mathcal {C}(G)$ be the set of cycle lengths in a graph $G$ and let $\mathcal {C}_{\mathrm {odd}}(G)$ be the set of odd numbers in $\mathcal {C}(G)$. We prove that, if $G$ has chromatic number $k$, then $\sum _{\ell \in \mathcal {C}_{\mathrm {odd}}(G)}1/\ell \geq (1/2-o_k(1))\log k$. This solves Erdős and Hajnal’s odd cycle problem, and, furthermore, this bound is asymptotically optimal.
In 1984, Erdős asked whether there is some $d$ such that each graph with chromatic number at least $d$ (or perhaps even only average degree at least $d$) has a cycle whose length is a power of 2. We show that an average degree condition is sufficient for this problem, solving it with methods that apply to a wide range of sequences in addition to the powers of 2.
Finally, we use our methods to show that, for every $k$, there is some $d$ so that every graph with average degree at least $d$ has a subdivision of the complete graph $K_k$ in which each edge is subdivided the same number of times. This confirms a conjecture of Thomassen from 1984.
References
- N. Alon and J. H. Spencer, The probabilistic method, John Wiley & Sons, 2004.
- Béla Bollobás, Cycles modulo $k$, Bull. London Math. Soc. 9 (1977), no. 1, 97–98. MR 441786, DOI 10.1112/blms/9.1.97
- Béla Bollobás and Andrew Thomason, Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs, European J. Combin. 19 (1998), no. 8, 883–887. MR 1657911, DOI 10.1006/eujc.1997.0188
- P. Erdős, Some recent progress on extremal problems in graph theory, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975, pp. 3–14. MR 0392671
- P. Erdős, Problems and results in graph theory, The theory and applications of graphs (Kalamazoo, Mich., 1980) Wiley, New York, 1981, pp. 331–341. MR 634537
- Paul Erdős, Some new and old problems on chromatic graphs, Combinatorics and applications (Calcutta, 1982) Indian Statist. Inst., Calcutta, 1984, pp. 118–126. MR 852032
- Paul Erdős, Some old and new problems in various branches of combinatorics, Discrete Math. 165/166 (1997), 227–231. Graphs and combinatorics (Marseille, 1995). MR 1439273, DOI 10.1016/S0012-365X(96)00173-2
- P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99. MR 193025, DOI 10.1007/BF02020444
- A. Gyárfás, Graphs with $k$ odd cycle lengths, Discrete Math. 103 (1992), no. 1, 41–48. MR 1171115, DOI 10.1016/0012-365X(92)90037-G
- A. Gyárfás, J. Komlós, and E. Szemerédi, On the distribution of cycle lengths in graphs, J. Graph Theory 8 (1984), no. 4, 441–462. MR 766494, DOI 10.1002/jgt.3190080402
- Jaehoon Kim, Hong Liu, Maryam Sharifzadeh, and Katherine Staden, Proof of Komlós’s conjecture on Hamiltonian subsets, Proc. Lond. Math. Soc. (3) 115 (2017), no. 5, 974–1013. MR 3733557, DOI 10.1112/plms.12059
- János Komlós and Endre Szemerédi, Topological cliques in graphs, Combin. Probab. Comput. 3 (1994), no. 2, 247–256. MR 1288443, DOI 10.1017/S0963548300001140
- János Komlós and Endre Szemerédi, Topological cliques in graphs. II, Combin. Probab. Comput. 5 (1996), no. 1, 79–90. MR 1395694, DOI 10.1017/S096354830000184X
- K. Kuratowski, Sur le probleme des courbes gauches en topologie, Fund. Math. 16 (1930), 271–283.
- Hong Liu and Richard Montgomery, A proof of Mader’s conjecture on large clique subdivisions in $C_4$-free graphs, J. Lond. Math. Soc. (2) 95 (2017), no. 1, 203–222. MR 3653090, DOI 10.1112/jlms.12019
- W. Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen, Math. Ann. 174 (1967), 265–268 (German). MR 220616, DOI 10.1007/BF01364272
- Wolfgang Mader, Hinreichende Bedingungen für die Existenz von Teilgraphen, die zu einem vollständigen Graphen homöomorph sind, Math. Nachr. 53 (1972), 145–150 (German). MR 498279, DOI 10.1002/mana.19720530113
- Benny Sudakov and Jacques Verstraëte, Cycle lengths in sparse graphs, Combinatorica 28 (2008), no. 3, 357–372. MR 2433007, DOI 10.1007/s00493-008-2300-6
- Benny Sudakov and Jacques Verstraëte, Cycles in graphs with large independence ratio, J. Comb. 2 (2011), no. 1, 83–102. MR 2847915, DOI 10.4310/JOC.2011.v2.n1.a3
- Carsten Thomassen, Subdivisions of graphs with large minimum degree, J. Graph Theory 8 (1984), no. 1, 23–28. MR 732014, DOI 10.1002/jgt.3190080103
- Horst Sachs (ed.), Graphs, hypergraphs and applications, Teubner-Texte zur Mathematik [Teubner Texts in Mathematics], vol. 73, BSB B. G. Teubner Verlagsgesellschaft, Leipzig, 1985. MR 869428
- Carsten Thomassen, Configurations in graphs of large minimum degree, connectivity, or chromatic number, Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985) Ann. New York Acad. Sci., vol. 555, New York Acad. Sci., New York, 1989, pp. 402–412. MR 1018651, DOI 10.1111/j.1749-6632.1989.tb22479.x
- Jacques Verstraete, Unavoidable cycle lengths in graphs, J. Graph Theory 49 (2005), no. 2, 151–167. MR 2137540, DOI 10.1002/jgt.20072
- J. Verstraëte, Extremal problems for cycles in graphs, Recent Trends in Combinatorics, Springer, 2016, pp. 83–116.
Bibliographic Information
- Hong Liu
- Affiliation: Extremal Combinatorics and Probability Group (ECOPRO), Institute for Basic Science (IBS), Daejeon, South Korea
- ORCID: 0000-0002-5735-7321
- Email: hongliu@ibs.re.kr
- Richard Montgomery
- Affiliation: Mathematics Institute, University of Warwick, Coventry CV4 7AL, United Kingdom
- MR Author ID: 1097544
- Email: richard.montgomery@warwick.ac.uk
- Received by editor(s): November 17, 2020
- Received by editor(s) in revised form: July 16, 2022
- Published electronically: March 31, 2023
- Additional Notes: The first author was supported by the Institute for Basic Science (IBS-R029-C4) and the UK Research and Innovation Future Leaders Fellowship MR/S016325/1. The second author was supported by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme (grant agreement No. 947978) and the Leverhulme trust.
- © Copyright 2023 by Hong Liu; Richard Montgomery.
- Journal: J. Amer. Math. Soc. 36 (2023), 1191-1234
- MSC (2020): Primary 05C38
- DOI: https://doi.org/10.1090/jams/1018
- MathSciNet review: 4618957