Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often

Statement

Does every graph $G$ with infinite chromatic number contain a cycle of length $2^n$ for infinitely many $n$? (Conjectured by Erdős, with the min-degree/average-degree finite form attributed to Erdős 1984; erdosproblems.com/63 also attributes a version to Mihók.) Erdős further remarked it is likely that $2^n$ can be replaced by any sufficiently rapidly growing sequence.

Facts

- Status: SOLVED, answer YES (erdosproblems.com/63, fetched 2026-07-02). - This is one instance of a family of related questions about which cycle lengths must appear in graphs of large/infinite chromatic number; the *easy* partial case — uncountable chromatic number — was already known via Erdős–Hajnal (1966): such a graph contains arbitrarily large complete bipartite subgraphs, which trivially force cycles of every even length. The hard case is *countably* infinite chromatic number, where no such easy bipartite structure is guaranteed. - Via the de Bruijn–Erdős compactness theorem, infinite chromatic number implies, for infinitely many $r$, a finite connected subgraph $G_r$ with chromatic number exactly $r$ — so the problem reduces to a *finitary* question: do graphs of arbitrarily large chromatic number (equivalently, after standard reductions, of arbitrarily large average degree) contain a cycle of length $2^n$ for arbitrarily large $n$? - This finitary question is exactly what Hong Liu and Richard Montgomery resolved in "A solution to Erdős and Hajnal's odd cycle problem," arXiv:2010.15802 (Oct 2020), published *J. Amer. Math. Soc.* 36 (2023), 1191–1234. Their headline result answers a 1981 Erdős–Hajnal question (is $\sum_{\ell\in C_{odd}(G)} 1/\ell$ necessarily infinite for infinite-chromatic-number $G$?) with the sharp bound: chromatic number $k$ $\Rightarrow$ $\sum_{\ell\in C_{odd}(G)}1/\ell \ge (1/2-o_k(1))\log k$, asymptotically optimal. - As a corollary of the same machinery, Liu–Montgomery simultaneously proved: (a) the Erdős 1984 power-of-2-cycle conjecture — sufficiently large average degree forces a cycle of length exactly $2^n$ for some large $n$ — which is the finitary engine behind #63; and (b) Thomassen's 1984 conjecture that large average degree forces a subdivision of a large complete graph with *uniformly* subdivided edges (gilkalai.wordpress.com, fetched). - Do not confuse with the Erdős–Gyárfás conjecture: "every graph with minimum *degree* 3 has a cycle whose length is a power of 2" (dwest.web.illinois.edu/openp/2powcyc.html, fetched) — a superficially similar but genuinely different and still OPEN statement (minimum-degree hypothesis, not average-degree/chromatic-number hypothesis; known only for restricted classes, e.g. planar claw-free graphs). #63's resolution does not touch it. - Related problem: Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle (listed as related on erdosproblems.com/63).

Solution

Answer: YES. Every graph of infinite chromatic number contains a cycle of length $2^n$ for infinitely many $n$ — in fact Liu–Montgomery's finite theorem gives the stronger statement that sufficiently large *average degree* (not just chromatic number) already forces such a cycle, and their odd-cycle bound shows the reciprocal-sum divergence Erdős–Hajnal asked about in 1981.

The transferable technique — (robust) sublinear expanders as a universal embedding tool.

1. Reduce chromatic number to average degree. By de Bruijn–Erdős compactness, infinite chromatic number gives finite subgraphs of arbitrarily large chromatic number; standard degeneracy arguments then extract subgraphs of arbitrarily large *average degree* (a graph with chromatic number $k$ has a subgraph of average degree $\ge k-1$). This turns an infinitary/topological statement into a finite extremal-graph-theory question: "what does large average degree force?"

2. Find a sublinear expander inside any dense-enough graph. Komlós & Szemerédi (1996) showed every graph contains a subgraph that is a *sublinear expander* — informally, a subgraph in which every not-too-large, not-too-small vertex subset $S$ has neighborhood growing by a factor that shrinks only sublinearly as $|S|$ grows (rather than the constant-factor expansion of classical expanders) — with average degree comparable to the host graph's. Haslegrave, Kim & Liu strengthened this to a *robust* sublinear expander, which retains its expansion property even after deleting a modest number of edges — the version actually needed for delicate embedding arguments (gilkalai.wordpress.com, fetched).

3. Embed the target structure by BFS-tree growth inside the expander. Sublinear expansion is exactly the property that lets you grow a breadth-first search tree from a vertex whose ball sizes roughly double at each step (because each ball of moderate size expands by a sublinear-but-still-superconstant factor), letting you *control path lengths precisely* — reach a set of prescribed size at a prescribed depth, and connect two BFS trees by a path of a *chosen* length (mod small correction terms). This is the mechanism that converts "large average degree" into "cycles of essentially every sufficiently large length," and in particular into a cycle of length exactly $2^n$: run the doubling BFS growth for $n$ steps and close it up. 4. Why this cracked a 40-year-old problem. Earlier attacks tried to build the required cycle length directly via regularity-lemma/absorption-style arguments, which lose control of *exact* path length (regularity gives approximate, not exact, structure). The sublinear-expander framework instead gives *fine-grained, per-length* control for free, because BFS ball growth in a sublinear expander is itself an approximately-doubling process — matching the $2^n$ target structurally, not just numerically. The same tool, in the same paper, simultaneously cracked two other stalled conjectures (Thomassen's uniform-subdivision conjecture, Erdős–Hajnal's 1981 odd-cycle reciprocal-sum question), which is direct evidence the technique is a general-purpose embedding hammer rather than a bespoke trick for one cycle-length statement. 5. Portable takeaway. Whenever an open problem has the shape "large average degree / chromatic number forces [some prescribed finite substructure, especially one indexed by a length/size parameter]," (robust) sublinear expanders — Komlós–Szemerédi 1996, robustified by Haslegrave–Kim–Liu, weaponized for exact-length embedding by Liu–Montgomery 2020 — are now the leading first-attempt technique; see the survey "Sublinear Expanders and Their Applications" (Liu, *Surveys in Combinatorics* 2024) for the general toolkit before attempting a bespoke argument.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — listed as the directly related problem on erdosproblems.com/63 (same cycles/chromatic-number neighborhood). - concept/sublinear-expanders — Komlós–Szemerédi (1996) existence result + Haslegrave–Kim–Liu robust version; the core reusable tool behind this solution and behind several other post-2018 extremal graph theory breakthroughs (clique subdivisions, cycle decompositions, Ramsey goodness). - De Bruijn–Erdős compactness theorem — infinite chromatic number is determined by finite subgraphs — the compactness step that reduces "infinite chromatic number" to "arbitrarily large finite chromatic number," making the problem finitary and hence attackable by expander/embedding methods. - concept/erdos-gyarfas-conjecture — the superficially similar but distinct and still-open minimum-degree-3 power-of-2-cycle conjecture; do not conflate with #63's average-degree/chromatic-number version, which is solved.