Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree)

Statement

Let $G$ be a graph with minimum degree $\delta(G)=k$ (equivalently, in the original phrasing, $n$ vertices and $\ge kn$ edges — a graph of edge-density $\ge k$ contains a subgraph of minimum degree $>k$), and let $a_1<a_2<\cdots$ be the distinct cycle lengths occurring in $G$, i.e. $C(G)=\{a_1,a_2,\dots\}$. Write $L(G)=\sum_i 1/a_i$. Erdős asked how $f(\alpha):=\inf\{L(G):|E(G)|\ge \alpha|V(G)|\}$ behaves as $\alpha\to\infty$; the complete bipartite graphs $K_{\alpha,\alpha}$ (only even cycle lengths, roughly $2,4,\dots,2\alpha$) show $f(\alpha)\ll\log\alpha$. Erdős and Hajnal conjectured the matching lower bound: \[\sum_i \frac1{a_i} \gg \log k.\] (erdosproblems.com/65 states the problem exactly this way; the same $\log k$ bound in the *chromatic-number* / *odd-cycle-only* form — $\chi(G)=k\Rightarrow\sum_{a_i \text{ odd}} 1/a_i\gg\log k$ — is the distinct sibling problem erdos/57.) A genuinely separate, still-open second question is appended on erdosproblems.com/65: is $L(G)$ actually *minimised* by complete bipartite graphs (the extremal-graph question, sharper than just the asymptotic rate)? This page is about the first question — the $\gg\log k$ rate — which is fully solved; the second (extremal-graph) question remains open, hence erdosproblems.com lists #65's overall page status as OPEN even though its headline inequality is a theorem.

Facts

- Origin: Erdős raised this across [Er74d, "Unsolved Problems," 1974], [Er75, "Some recent progress on extremal problems in graph theory," Congr. Numer.], [Er81, "On the combinatorial problems which I would most like to see solved," Combinatorica], [Er93,p.342], [Er95] (bib details fetched from erdosproblems.com/bibs/*); jointly attributed to Erdős and Hajnal. It is #65 in the "Extremal Graph Theory" section of the graphs problem collection (erdosproblems.com/65). - Solved (rate) by Gyárfás, Komlós, Szemerédi, 1984 (GKS84, *J. Graph Theory* 8, 441–462, MR766494): Theorem 4 of that paper proves exactly $L(G)\ge a\log[\delta(G)]$ for $\delta(G)\ge b$, for explicit (if large) constants $a,b>0$ — this is the Erdős–Hajnal conjecture, proved with an unspecified small constant $a$. - Sharp constant obtained by Liu & Montgomery, 2020 (arXiv:2010.15802, published *J. Amer. Math. Soc.* 36 (2023) 1191–1234): as a corollary of the machinery they built to solve the sibling odd-cycle/chromatic-number problem erdos/57, they prove the asymptotically optimal bound $L(G)\ge(\tfrac12-o(1))\log k$ for $\delta(G)\ge k$ — matching, up to the $o(1)$, the $K_{k,k}$ upper-bound construction, so the constant $\tfrac12$ in front of $\log k$ is essentially best possible (erdosproblems.com/65, remarks; cross-confirmed on the already-existing local pages erdos/64.md line 24 and erdos/63.md). - What remains open: only the *second* question on erdosproblems.com/65 — whether $L(G)$ is exactly minimised by complete bipartite graphs (a finer, non-asymptotic extremal statement). erdosproblems.com/65 remarks that Montgomery's survey mentions forthcoming work of Montgomery, Milojević, Pokrovskiy, and Sudakov proving an extremal-graph statement of this shape for $k$ sufficiently large (the site's own wording says "maximised," which looks like it may be a slip for "minimised" relative to the problem statement's own wording — flagged here as an unresolved textual ambiguity in the source, not independently verified against the forthcoming paper itself, which was not found on arXiv at time of writing). - Related problems: erdos/57 (chromatic-number/odd-cycle sibling, fully PROVED by the same [LiMo20] paper), Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often and Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle (power-of-2-cycle problems resolved by the same Liu–Montgomery machinery, already documented in this wiki with concept slug concept/sublinear-expanders).

Solution

Answer: yes, $\sum_i 1/a_i \gg \log k$ — proved by Gyárfás–Komlós–Szemerédi (1984) with an unspecified constant, then sharpened to the asymptotically tight constant $\tfrac12$ by Liu–Montgomery (2020) via a completely different, later technique. Two independent proof techniques exist for this bound; both are transferable, and they generalize in different directions, so both are recorded here.

Technique 1 (the original 1984 proof — the one that first cracked it): branching trees ("$\tfrac13$-trees") + a crown lemma + a difference-set covering lemma, chained by dyadic-scale harmonic summation.

1. Force exponential branching via a "$\tfrac13$-tree." From a graph of minimum degree $\delta$, greedily grow a rooted tree $T$ level by level so that at every level $L_i$, at least a $\tfrac13$-fraction of the vertices have $\ge2$ children in $L_{i+1}$ (a *$\tfrac13$-tree*). Because minimum degree is large, such branching is always extractable from a suitable subgraph; it forces $|L_i|$ to grow roughly geometrically in $i$, so the tree height needed to reach $\Theta(n)$ leaves is only $O(\log n)$ (GKS84 §2, "the $i$-trees and their crowns"). 2. Exploit the "crown": the non-tree edges among $\mathrm{top}(T)$ (the leaves) and nearby levels, guaranteed to be plentiful because $\delta(G)$ bounds the degree of every leaf and only $O(1)$ of that degree is used by tree edges. Partitioning the crown edges by which of three target sets they land in (back to other leaves, to lower levels, etc.) and pigeonholing (Lemma 1/Lemma 2 in GKS84) produces a *dense* sub-crown $F_1$ of controlled minimum degree. 3. Turn crown structure into a spread of cycle lengths via a number-theoretic covering lemma. A long path $P=(x_1,\dots,x_r)$ inside the dense crown, with alternating vertices $Y=\{x_1,x_3,\dots\}$ split by the tree structure into two sets $Y_1,Y_2$, is combined with Lemma 3 — a purely combinatorial fact about difference sets: for any partition $(U,V)$ of $\{1,\dots,n\}$, the difference set $D(U,V)=\{|u-v|:u\in U,v\in V\}$ contains *all* residues up to $n/3$ except possibly multiples of some single integer $m$. Applying this to the indices of $Y_1$ vs. $Y_2$ along the path shows that cycles $H(p,q)$ built from "tree-path back to a common ancestor" + "crown-path along $P$" realize almost every even length in a whole interval $[2h'+2,\ \tfrac13(r+1)]$, where $h'$ is (twice) the tree height — i.e. $C(G)$ is forced to be dense (not just nonempty) in a range whose *ratio of endpoints is large* (Theorem 2/2' of GKS84). 4. Convert "many cycle lengths densely packed in $[A,B]$" into a $\log(B/A)$ lower bound on $\sum 1/a_i$ — the key generic move. This is elementary but the crux of why the answer is $\log k$ rather than a constant: if (almost) every even integer in $[A,B]$ is an achievable cycle length, split $[A,B]$ into $O(\log(B/A))$ dyadic blocks $[2^jA,2^{j+1}A]$; each block of length $\sim 2^jA$ contributes $\Theta(1)$ to $\sum 1/a_i$ (since it holds $\Theta(2^jA)$ achievable lengths each $\asymp 2^jA$, so each block's contribution is a constant, independent of scale) — summing $\Theta(1)$ over $\Theta(\log(B/A))$ dyadic blocks gives $L(G)\gg\log(B/A)$ (GKS84 Proposition 1). This is exactly the harmonic-series-over-geometric-scales trick: a set with $\Theta(\log(B/A))$ "octaves" each containing $\Theta(1)$ worth of reciprocal-sum mass has total reciprocal sum $\Theta(\log(B/A))$. 5. Iterate across scales to reach $\log\delta(G)$, not just $\log(B/A)$ for one fixed subgraph. Since $\delta(F_1)\gtrsim\delta(G)$ up to a bounded constant loss and $|V(G)|$ can be enormous relative to $\delta(G)$, a single application only yields a bound in terms of $\log(B/A)$ for the *specific* interval found. GKS84's Theorem 3+4 close this gap by an inductive peeling argument: repeatedly pass to a subgraph of roughly half the previous minimum degree (via Corollary 4, itself a longest-path/inner-vertex trick — Lemma 4) whenever the direct bound is not yet strong enough, accumulating $\Theta(1)$ of reciprocal-sum mass at each of $\Theta(\log\delta(G))$ scales, and taking the better of "many small contributions" vs. "one big contribution at the bottom scale" (the case split in the proof of Theorem 4). The net effect: $L(G)\ge a\log[\delta(G)]$ for absolute constants $a,b$ whenever $\delta(G)\ge b$. 6. Why this is the transferable idea. The generic shape — *(exponential branching structure) $\Rightarrow$ (dense spread of achievable "lengths" in a wide interval) $\Rightarrow$ (dyadic/geometric-scale harmonic summation turns "density in $[A,B]$" into $\Theta(\log(B/A))$)* — is a reusable three-step template for *any* problem of the form "show a reciprocal-sum-of-achievable-sizes statistic grows like $\log(\text{some parameter})$," not just for cycle lengths in graphs. The dyadic-harmonic-summation step (step 4) in particular is fully general: whenever one can show a combinatorial structure realizes (almost) every element of some size-class in a range $[A,B]$, the reciprocal-sum-over-that-range is automatically $\Theta(\log(B/A))$, for free, regardless of the combinatorial mechanism that produced the density.

**Technique 2 (the 2020 sharpening — a different, more modern route to a *better constant*): sublinear expanders.** Liu & Montgomery (arXiv:2010.15802) do not use branching trees at all; instead they extract a *robust sublinear expander* subgraph (Komlós–Szemerédi 1996 existence theorem, robustified by Haslegrave–Kim–Liu) and grow BFS balls inside it, whose sizes expand by a controllable, near-arbitrary factor at each step — this gives *exact-length* control over realizable cycle lengths across essentially the *entire* range up to $\delta(G)$-driven bounds (not just a bounded-ratio window), which is what pushes the constant from GKS84's unspecified $a$ up to the tight $\tfrac12$. This technique — already the featured solution on the sibling pages erdos/57/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 in this wiki — is the *general-purpose* modern hammer for "large degree/chromatic number forces a prescribed-length substructure" problems, whereas GKS84's tree-branching+dyadic-harmonic technique is older, more elementary, self-contained, and specifically well-suited to problems phrased as reciprocal-sum lower bounds via density-in-an-interval, without needing the heavier expander machinery.

Bottom line for downstream use: two independently reusable tricks are exported from this problem — (i) the *dyadic/geometric-scale harmonic-summation* argument (step 4 above), the cheapest way to convert "structure realizes a dense range of sizes" into a $\log$-scale reciprocal-sum bound, applicable far outside graph theory; and (ii) *sublinear expanders* for exact-length embedding at scale, the state-of-the-art tool for degree-forces-substructure problems generally (see concept/sublinear-expanders, documented via erdos/63.md).

Related

- erdos/57 — the chromatic-number/odd-cycle-only sibling ($\chi(G)=k\Rightarrow\sum_{\text{odd }a_i}1/a_i=\infty$, sharpened to $\ge(\tfrac12-o(1))\log k$); fully PROVED by the same [LiMo20] paper that supplies the sharp constant here. - Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — infinite chromatic number forces cycles of length $2^n$ infinitely often; solved by the identical Liu–Montgomery sublinear-expander machinery. - Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — related power-of-2/prescribed-length cycle-forcing problem; explicitly notes (erdos/64.md) that [LiMo20] "gives the sharp asymptotic bound for erdos/65." - concept/sublinear-expanders — the Komlós–Szemerédi (1996) / Haslegrave–Kim–Liu robust-expander tool powering the 2020 sharp-constant proof; already the featured concept page from erdos/63.md. - concept/dyadic-harmonic-summation — the transferable "density-in-$[A,B]$ $\Rightarrow$ $\Theta(\log(B/A))$ reciprocal sum" trick (GKS84 Proposition 1), the core reusable idea of the *original* 1984 proof, independent of expanders. - concept/branching-tree-crown-argument — the GKS84 $\tfrac13$-tree + crown + difference-set-covering (Lemma 3) machinery itself, the concept page for the full original technique.