Liu–Montgomery (2020/2023) — Erdős–Hajnal odd-cycle reciprocal-sum problem

Statement

In 1966/1981 Erdős and Hajnal asked [ErHa66, Er81]: if $G$ is a graph with infinite chromatic number and $a_1<a_2<\cdots$ are the lengths of the odd cycles occurring in $G$, must $$\sum_i \frac{1}{a_i} = \infty\,?$$ Erdős called this a "much deeper question" than the analogous statement for *all* cycle lengths under an average-degree hypothesis (which Gyárfás–Komlós–Szemerédi had already settled in 1984, see Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree)), because average degree says nothing about odd cycles at all (bipartite graphs have arbitrarily high average degree and no odd cycles whatsoever) — the only hypothesis that can force odd-cycle density is on the chromatic number. This is erdosproblems.com problem #57 [ErHa66] [Er69b] [Er74d] [Er81] [Er90] [Er93,p.342] [Er94b] [Er95] [Er95d] [Er96] [Er97b] [Va99,3.58].

Facts

- Status: PROVED (erdosproblems.com/57). Conjectured by Erdős and Hajnal [ErHa66]; solved by Hong Liu and Richard Montgomery, "A solution to Erdős and Hajnal's odd cycle problem," arXiv:2010.15802 (submitted 2020-10-29), published *J. Amer. Math. Soc.* 36 (2023), 1191–1234. - Quantitative answer: if $G$ has chromatic number $k$, then $\sum_{\ell\in C_{\text{odd}}(G)} 1/\ell \ge (1/2 - o_k(1))\log k$ (arXiv:2010.15802, Theorem 1.4 + Corollary 1.5 specialized to residue $1 \bmod 2$). This is asymptotically optimal: complete balanced bipartite-like extremal examples pin the constant $1/2$ as best possible, matching the tight constant separately obtained for the all-cycle/average-degree sibling problem Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree). - Prior partial progress: Gyárfás (1992) showed $\chi(G)\ge 2k+1 \Rightarrow |C_{\text{odd}}(G)|\ge k$ (many distinct odd lengths, but no reciprocal-sum bound). Sudakov–Verstraete showed $\sum 1/\ell\to\infty$ only under the much stronger extra hypothesis that $G$'s independence ratio is not too small. Before Liu–Montgomery, no unconditional progress existed on the reciprocal sum itself. - The actual theorem proved is much stronger than the reciprocal-sum statement: Theorem 1.4 of arXiv:2010.15802 shows that for every $\varepsilon>0$ there is $k_0$ such that every graph $G$ with $\chi(G)=k\ge k_0$ contains every odd integer in a whole interval $[\ell,\, \ell\cdot k^{1-\varepsilon}]$ as a cycle length, for some $\ell\in\mathbb N$. Since the harmonic sum of the odd integers in $[\ell,\ell k^{1-\varepsilon}]$ diverges as $k\to\infty$ for every $\ell$, this immediately implies the 1981 conjecture — the reciprocal-sum question is derived as a corollary of a much more precise "interval of achievable lengths" theorem, not attacked head-on. - Same paper, same machinery, three further results: (i) Theorem 1.1 — the analogous *even*-cycle statement under an average-degree hypothesis (every average-degree-$d$ graph contains every even length in $[\log^8\ell,\ell]$ for some $\ell\ge d/(10\log^{12}d)$), which reproves and sharpens Gyárfás–Komlós–Szemerédi's 1984 bound to the tight constant $1/2$ (this sharpened bound is the content of Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree)); (ii) resolution of Erdős's 1984 question on whether powers of $2$ (and more generally any exponentially-bounded increasing sequence) are unavoidable as cycle lengths under an average-degree condition (Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often, Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle); (iii) proof of Thomassen's 1984 conjecture that high average degree forces a balanced subdivision of $K_k$ (every edge subdivided into a path of the *same* length $\ell$). - Still open beyond this result (per erdosproblems.com/57, remarks by Erdős himself): must the odd cycle lengths $a_i$ have positive upper density? Erdős further speculated (in [Er95d],[Er96]) whether the upper density — or even the upper *logarithmic* density — must be $\ge 1/2$. The *lower* density can be $0$, witnessed by graphs of arbitrarily large chromatic number and large girth (so the reciprocal-sum divergence in the theorem is compatible with long odd-cycle-free initial stretches).

Solution

Answer: yes — proved via a completely new constructive method (sublinear expanders + a novel "adjuster" gadget), not via the branching-tree/dyadic-summation method that had solved the easier average-degree sibling problem in 1984.

The key difficulty that had stalled progress since 1981: an average-degree hypothesis gives you a dense *local* neighborhood structure everywhere, which classical branching-tree arguments (Gyárfás–Komlós–Szemerédi) can exploit directly. A chromatic-number hypothesis gives you no such local density guarantee — a graph can have arbitrarily high chromatic number while remaining sparse and having large girth (no short cycles at all locally). Liu–Montgomery's route is to first solve a *precise, exact-length-control* even-cycle embedding problem under average degree (their Theorem 2.7/1.1), and only then bootstrap chromatic number into average degree by a bipartite-decomposition/edge-replacement argument (their Theorem 1.4) — the "much deeper" step Erdős anticipated.

The transferable idea, in four layers

1. Extract a robust sublinear expander from any graph (Komlós–Szemerédi 1996). Every graph $G$ contains a subgraph $H$ with comparable average degree ($d(H)\ge d(G)/2$, $\delta(H)\ge d(H)/2$) that is an $(\varepsilon_1,k)$-*expander*: every vertex set $X$ with $k/2\le|X|\le|H|/2$ satisfies $|N(X)|\ge \varepsilon(|X|)\cdot|X|$ where $\varepsilon(x)=\Theta(1/\log^2 x)$ — a much *weaker* (sublinear-rate) expansion than classical constant-degree expanders, but one guaranteed to exist inside literally *any* graph, sparse or dense, high-girth or not. This is the load-bearing "expansion always exists somewhere" fact that lets the argument bypass the local-density requirement that blocked classical methods.

2. Turn one short cycle into an "adjuster": a gadget that shifts path length by exactly $\pm2$. If $H$ contains a short cycle $C$ of length $2\ell$ avoiding target endpoints $x,y$, pick two vertices $v_1,v_2$ on $C$ at distance $\ell-1$: going around $C$ the short way vs. the long way gives two $v_1,v_2$-paths whose lengths differ by exactly $2$. Attaching vertex-disjoint connector trees $F_1,F_2$ (each a BFS-ball structure of depth $O(\log^3 n)$, built by *expanding* $v_1$ and $v_2$ outward until they meet $x$ and $y$) turns this into an $x,y$-path whose length can be dialed up or down by $2$ at will. Chaining $\Theta(\log^3 n)$ such adjusters along a connecting path lets the $x,y$-path length be tuned to any specific value of the right parity in a wide target interval — this is what converts "expansion exists" into "every length in an interval is exactly realizable," the qualitative leap beyond merely proving *some* long cycle exists.

3. The genuinely new technical innovation — robust gadget construction against sublinear (not linear) expansion. Because the expansion rate $\varepsilon(x)=\Theta(1/\log^2 x)$ decays as $x$ grows, the naive "just expand a ball until it's an adjuster" argument can fail: expanding a set $A_v$ around any single candidate vertex $v$ might get *locally stuck* against an obstacle set $W$ without violating the graph's overall expansion (sublinear-rate expansion of a union of many stuck sets is not a contradiction to each individual set failing to expand, since $\varepsilon$ is sub-additive across scales). Liu–Montgomery's fix: if *many* candidate vertices $v$ each produce a stuck set $A_v$, pigeonhole on the *size* $|A_v|$ and on the *external neighborhood* $N(A_v,W)\subseteq W$ (using the graph's $TK^{(2)}_{d/2}$-free structural condition, which caps $|N(A_v,W)|\le|A_v|^2$) to find many stuck sets of the *same* size sharing the *same* small external footprint; their union $A=\bigcup A_v$ is then large enough, at the *same* logarithmic scale, that the sublinear expansion bound applied to $A$ directly *does* contradict every individual $A_v$ being stuck — a genuine construction rather than an existence-only compactness argument. This scale-matching pigeonhole trick is the technical heart of the paper (Section 2.6) and is what makes the sublinear-expander machinery *usable* for exact, robust (obstacle-avoiding) gadget placement rather than just soft existence proofs.

4. Bootstrap chromatic number into average degree by decomposing into bipartite "interval gadgets" and rerouting a minimal odd cycle. Applying steps 1–3 gives: any graph of average degree $d$ contains a bipartite subgraph $H$ in which *every edge* $uv$ can be individually replaced by a path of any length (of matching parity) in a wide interval $[\log^8\ell_H,\ell_H]$. Given $\chi(G)=k$ large, greedily extract a maximal edge-disjoint family of such bipartite "replaceable-edge" gadgets from $G$; a chromatic-number argument (if the family weren't maximal, the leftover graph would still have high chromatic number, forcing another gadget to exist) shows the union of gadgets contains some odd cycle $C$. Replacing several vertex-disjoint edges of $C$ by paths of many different lengths, drawn independently from each edge's gadget interval, produces odd cycles of many different total lengths spanning a wide interval — yielding Theorem 1.4's interval-of-odd-lengths statement, and hence, by direct summation, the 1981 conjecture.

Why this cracked a 39-year-open problem: the 1984 Gyárfás–Komlós–Szemerédi technique for the average-degree/all-cycles sibling relies on branching trees that need genuine local density everywhere — a hypothesis chromatic number simply does not supply (high-girth graphs can have arbitrarily large chromatic number). Sublinear expanders sidestep this because *every* graph, including sparse high-girth ones, contains one; the adjuster+robust-gadget-construction machinery then supplies the missing *exact-length* control that a soft existence argument (e.g. plain Komlós–Szemerédi path-connection lemmas) cannot give on its own. The chromatic-number bootstrap (step 4) is then a comparatively short reduction once the average-degree engine (steps 1–3) is available — matching Erdős's own remark that the odd-cycle/chromatic-number question was the deep part, with the average-degree/all-cycle question already tractable by older methods.

Bottom line for downstream use: sublinear expanders (Komlós–Szemerédi existence + Liu–Montgomery's robust, obstacle-avoiding gadget-construction pigeonhole trick) are now the general-purpose hammer for "large chromatic number / average degree forces a cycle (or subdivision, or other length-structured subgraph) of a *prescribed* length or in a *prescribed* interval." This is the concept page to link as `concept/sublinear-expanders; the specific gadget-placement pigeonhole innovation is concept/adjuster-gadget-construction`.

Related

- Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) — the average-degree/all-cycle-lengths sibling ($\delta(G)\ge k\Rightarrow\sum 1/a_i\gg\log k$); solved first by Gyárfás–Komlós–Szemerédi (1984, unspecified constant) via a *different* branching-tree/dyadic-summation technique, then sharpened to the tight constant $1/2$ by this same Liu–Montgomery paper as a byproduct (Theorem 1.1/Corollary 1.2). - Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — infinite chromatic number forces cycles of length $2^n$ infinitely often; resolved by the identical sublinear-expander machinery documented here. - Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — related power-of-2/prescribed-length cycle-forcing problem, same toolkit. - concept/sublinear-expanders — the Komlós–Szemerédi (1996) existence theorem for weak/sublinear-rate expanders inside any graph; the load-bearing tool. - concept/adjuster-gadget-construction — the robust, obstacle-avoiding pigeonhole construction (Section 2.6 of arXiv:2010.15802) that turns soft sublinear expansion into exact, targeted length control; the paper's chief technical innovation. - concept/dyadic-harmonic-summation — the older (1984) technique this problem's sibling Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) was originally solved with; useful contrast showing two structurally different routes to "$\Rightarrow\log k$" bounds. - Thomassen's balanced-subdivision conjecture (1984) — proved as a third corollary of the same machinery in arXiv:2010.15802 (Theorem 1.7); not yet a separate page in this wiki.