# Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.83.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

## A solution to Erdős and Hajnal’s odd cycle problemHTML 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

## 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
Similar Articles
• Retrieve articles in Journal of the American Mathematical Society with MSC (2020): 05C38
• Retrieve articles in all journals with MSC (2020): 05C38
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.