The Library
A solution to Erdős and Hajnal’s odd cycle problem
Tools
Tools
Tools
Liu, Hong and Montgomery, Richard (2023) A solution to Erdős and Hajnal’s odd cycle problem. Journal of the American Mathematical Society . doi:10.1090/jams/1018 ISSN 1088-6834. (In Press)
|
PDF
WRAP-solution-Erdős-Hajnals-odd-cycle-problem-22.pdf - Accepted Version - Requires a PDF viewer. Download (753Kb) | Preview |
Official URL: https://doi.org/10.1090/jams/1018
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 C(G) be the set of cycle lengths in a graph G and let Codd(G) be the set of odd numbers in C(G). We prove that, if G has chromatic number k, then ∑ℓ∈Codd(G)1/ℓ≥(1/2−ok(1))logk. 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 Kk in which each edge is subdivided the same number of times. This confirms a conjecture of Thomassen from 1984.
| Item Type: | Journal Article | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Combinatorial analysis | |||||||||||||||
| Journal or Publication Title: | Journal of the American Mathematical Society | |||||||||||||||
| Publisher: | American Mathematical Society | |||||||||||||||
| ISSN: | 1088-6834 | |||||||||||||||
| Official Date: | 2023 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| DOI: | 10.1090/jams/1018 | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | In Press | |||||||||||||||
| Reuse Statement (publisher, data, author rights): | First published in Journal of the American Mathematical Society in [volume/issue number and year], published by the American Mathematical Society,” and the copyright notice in proper form must be placed on all copies. | |||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
| Copyright Holders: | © Copyright 2023 by Hong Liu; Richard Montgomery. | |||||||||||||||
| Date of first compliant deposit: | 30 November 2022 | |||||||||||||||
| Date of first compliant Open Access: | 30 November 2022 | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||
| Related URLs: | ||||||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
