Large min/average degree forces a wide interval of cycle lengths (Liu–Montgomery robust-expander embedding)

Statement

Theorem 1.1 (Liu–Montgomery 2020, arXiv:2010.15802). There is $d_0>0$ such that: if $G$ is a graph with average degree $d\ge d_0$, then there is some $$ \ell \ge \frac{d}{10\log^{12}d} $$ such that the cycle-length set $C(G)$ contains every even integer in the interval $[\log^{8}\ell,\ \ell]$.

Two structurally identical companion results come out of the same machine:

- Theorem 1.4 (chromatic-number / odd-cycle form). For each $\varepsilon>0$ there is $k_0$ such that for all $k\ge k_0$: if $\chi(G)\ge k$, then $C(G)$ contains every odd integer in some interval $[\ell,\ \ell\cdot k^{1-\varepsilon}]$. This resolves the 1981 Erdős–Hajnal odd-cycle problem: $\sum_{\ell\in C_{odd}(G)}1/\ell\to\infty$ as $\chi(G)\to\infty$, with the asymptotically sharp rate $\ge(\tfrac12-o_k(1))\log k$ (Corollary derived jointly with Theorem 1.1's harmonic-sum corollary, matching the $K_{k,k}$ upper bound). - Theorem 1.7 (Thomassen's balanced-subdivision conjecture, 1984). For each $k\in\mathbb N$ there is $d$ such that every graph with average degree $\ge d$ contains $TK_k^{(\ell)}$ for some $\ell$ — a subdivision of $K_k$ in which every edge is replaced by a path of the same length $\ell$.

When it applies. Any question of the shape *"does sufficiently large average degree (or chromatic number, via a reduction) force a cycle/path of some specific or wide-range length?"* This is now the default first tool for that shape of problem — see 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, Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree), all resolved or sharpened by this single 2020 result.

Facts

- Precise regime. The forced interval $[\log^8\ell,\ell]$ has $\ell$ roughly linear in $d$ (up to a $\log^{12}d$ loss), so the *ratio* of largest to smallest forced cycle length is huge — $\Omega(d/\mathrm{polylog}(d))$ — not just a bounded-width window. This is what makes the result strong enough to force *every* power of 2 (Corollary 1.3: any sequence $\sigma_i$ with $\sigma_{i+1}\le\exp(\sigma_i^{1/10})$ is "unavoidable with high average degree"), resolving Erdős's 1984 power-of-2-cycle question and a question of Sudakov–Verstraëte. The exponent $1/10$ is not optimal but the paper shows it cannot be pushed past $1/3$ with this connection method (§2.4.4). - Corollary: sharp harmonic-sum bound. Because the even integers in $[\log^8\ell,\ell]$ are dense, summing $1/\ell$ over a set that's dense in a huge dyadic range gives $\sum_{\ell\in C(G)}1/\ell \ge (\tfrac12-o_d(1))\log d$ — improving Gyárfás–Komlós–Szemerédi's 1984 unspecified-constant bound to the asymptotically tight constant $\tfrac12$, confirming a conjecture of Erdős. (This is the same "density-in-$[A,B]$ $\Rightarrow \Theta(\log(B/A))$ reciprocal sum" trick documented on Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree); Liu–Montgomery gets a *sharper* interval than GKS84's tree-branching argument, hence a sharper constant.) - Base tool: (sublinear) expanders exist inside every graph, essentially for free. Komlós & Szemerédi (1994/1996) proved every graph $G$ has a subgraph $H$ that is an $(\varepsilon_1,k)$-expander with $d(H)\ge d(G)/2$, $\delta(H)\ge d(H)/2$ — i.e. you never lose more than a constant factor of average degree by passing to the expander. Definition 2.1 (Liu–Montgomery, verbatim from the paper): $G$ is an $(\varepsilon_1,k)$-expander if $|N(X)|\ge \varepsilon(|X|,\varepsilon_1,k)\cdot|X|$ for all $X$ with $k/2\le|X|\le|G|/2$, where $\varepsilon(x,\varepsilon_1,k)=0$ for $x<k/5$ and $\varepsilon_1/\log_2^2(15x/k)$ for $x\ge k/5$ — i.e. expansion rate decays only *poly-logarithmically*, not polynomially, as the set grows, which is what "sublinear expander" means as opposed to a classical constant-rate expander. This is a strictly weaker, much more universally-available property than linear/constant-degree expansion. - Robust sublinear expanders (Haslegrave, Kim & Liu, "Extremal density for sparse minors and subdivisions," IMRN 2022, 15505–15548) strengthen this to survive edge deletion. Definition (WebSearch-corroborated): $G$ on $n$ vertices is a robust sublinear expander if for every $0\le\varepsilon\le1$, every nonempty $U\subseteq V(G)$ with $|U|\le n^{1-\varepsilon}$, and every edge set $F$ with $|F|\le(\varepsilon/3)d(G)|U|$, the neighborhood in the *edge-deleted* graph still satisfies $|N_{G-F}(U)|\ge(\varepsilon/3)|U|$. This "robustness under adversarial edge removal" is exactly what lets an embedding argument re-route around vertices/edges already used by a partially-built structure — indispensable once you are simultaneously building many disjoint gadgets (paths, adjusters, subdivision branches) inside the same host expander, as Liu–Montgomery's proof does. (Robustness is used implicitly throughout Liu-Montgomery's §2.4-2.6 "avoid a used vertex set $U$" constructions, which is the concrete mechanism this survey-level naming captures.) - Bottleneck of the method: $\Theta(\log^3 n)$ connection paths. Any two vertices in an $(\varepsilon_1,\varepsilon_2 d)$-expander are joined by a path of length $O_{\varepsilon_1}(\log^3 n)$ (Liu–Montgomery Lemma 3.4). This is the source of the $\log^8\ell$ lower end of the forced interval, and the paper states explicitly that the interval's lower bound "cannot be reduced below $\Omega(\log^3 n)$ while using connection methods with this graph expansion" — i.e. the polylog slack in the theorem is intrinsic to the expander-connectivity mechanism, not a slack the authors merely failed to optimize away.

Technique

When to reach for it. The problem has the shape: "large min-degree / average-degree / chromatic number $\Rightarrow$ a cycle (or path, or subdivision) of [a specific length / every length in a range / every length in some prescribed sequence]." Classic examples already in this wiki: Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often (infinite chromatic number $\Rightarrow$ cycle of length $2^n$ infinitely often), Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle (min degree $\ge3$ $\Rightarrow$ power-of-2 cycle — Erdős–Gyárfás conjecture, still open in the *tight* min-degree-3 case but settled once degree exceeds an absolute constant), Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) (min degree $k$ $\Rightarrow \sum 1/a_i \gg \log k$ over achieved cycle lengths $a_i$).

The recipe, step by step (Liu–Montgomery's actual construction, §2.3-2.6)

1. Reduce to a bipartite expander. By Komlós–Szemerédi, extract from $G$ a subgraph $H$ that is an $(\varepsilon_1,k)$-expander with $d(H),\delta(H)=\Theta(d(G))$ — you lose only a constant factor of degree. A short further argument (Corollary 2.5) gets a *bipartite* expander subgraph, which is needed so that path lengths between two fixed vertices $x,y$ have a well-defined, controllable parity $\pi(x,y,H)\in\{0,1,2\}$ (Definition 2.6): the bipartition forces every $x$–$y$ path to have length $\equiv \pi(x,y,H)\pmod 2$, so you only ever need to hit *one* parity class of target lengths, not both. 2. Build "simple adjusters": short cycle $C$ (length $2\ell$) + attachment gadgets $F_1,F_2$. Pick two vertices $v_1,v_2$ at distance $\ell-1$ on $C$; the cycle gives *two* different $v_1$–$v_2$ paths whose lengths differ by exactly 2 (going the short way vs. the long way around $C$). Attach $x$ to $v_1$ and $y$ to $v_2$ via short connecting paths inside disjoint gadgets $F_1,F_2$ (each vertex within $O_{\varepsilon_1}(\log^3 n)$ of the attachment point, using expansion to guarantee such short connections exist and can dodge any bounded "already used" vertex set $U$). The result: two $x$–$y$ paths of lengths differing by exactly 2. 3. Chain $\Theta(\log^3 n)$ adjusters in sequence. Concatenating many such adjuster gadgets along one long $x$–$y$ path lets you choose, independently at each adjuster, whether to take the "$+0$" or "$+2$" detour — so the total path length can be dialed to any value in a range of width $\Theta(\log^3 n)$ around a base length, in increments of 2, all while respecting the fixed target parity. This is the mechanism that converts "expander exists" into "every length in a wide range is achievable," rather than just "some length is achievable." 4. The robust construction is the technical heart. Building 10m ≈ $\Theta(\log^3 n)$ *simultaneous, mutually vertex-disjoint* adjusters — each needing to dodge every vertex already used by every other adjuster and by the connecting backbone path — is only possible because the expansion property survives after removing the (bounded-size) set of already-used vertices/edges. This is precisely what "robust" sublinear expansion (Haslegrave–Kim–Liu) buys: an ordinary sublinear expander's expansion rate is a statement about the *original* graph, but the construction needs expansion in $H-U$ for a growing sequence of used-vertex sets $U$, which robustness guarantees stays effective as long as $U$ stays sub-linear in size. 5. Read off the theorem. Because $x$–$y$ paths of every length in $[\log^7 n,\ n/\log^{12}n]$ (matching target parity) exist in the bipartite expander (Theorem 2.7), adding back one edge $xy$ turns each such path into a cycle — giving every length in a shifted interval, which after tracking constants becomes Theorem 1.1's $[\log^8\ell,\ell]$. 6. Adapt for chromatic number instead of average degree (Theorem 1.4). Replace "large average degree" with "chromatic number $k$": a $TK_d^{(2)}$-subdivision structure (or the fact that removing any bipartite subgraph from $G$ still leaves average degree $\Omega(k)$, since $\chi(G)=k$ forces this) substitutes for the raw degree hypothesis, and the *same* adjuster-chaining machine runs inside it, now targeting odd lengths (because $TK^{(2)}$-type structures naturally realize odd path lengths between core vertices) to get every odd length in $[\ell,\ell\cdot k^{1-\varepsilon}]$. 7. Adapt for balanced subdivisions (Theorem 1.7). Instead of one $x$–$y$ pair, fix $k$ "core" vertices inside the expander and run the *same* adjuster construction $\binom{k}{2}$ times, once per pair, forcing all $\binom{k}{2}$ connecting paths to have the *same* length $\ell$ simultaneously — giving $TK_k^{(\ell)}$, confirming Thomassen's 1984 conjecture.

Why it works (core intuition). A sublinear expander lets you grow a BFS ball from any vertex so that its size increases by a (slowly shrinking but still super-constant) factor at every step; two such balls grown from $x$ and from a target point are therefore guaranteed to meet within $O(\log^3 n)$ steps, giving *short* connections between almost any two "not too large, not too small" vertex sets — even after some vertices are walled off, provided the expander is *robust*. Classical embedding tools (regularity lemma, absorption) give *approximate* structure: they tell you a long path or many disjoint paths exist, but not paths of an *exactly prescribed* length. Sublinear expansion, by contrast, gives *fine local surgery*: the adjuster gadget changes a specific path's length by exactly 2 without disturbing anything else, so lengths can be dialed precisely, one parity-preserving increment at a time, across a huge range. That precision — not just existence — is the entire reason this method cracked a problem (Erdős–Hajnal's 1981 odd-cycle question, and Erdős's 1984 power-of-2-cycle question) that had resisted regularity/absorption-style attacks for decades.

Recombination hooks. Any Erdős-style problem of the form "large [average degree / min degree / chromatic number] forces [a cycle / path / subdivision] of [a specific length or a whole class of lengths]" is a candidate: (a) pass to a (robust) sublinear expander subgraph, losing only a constant degree factor; (b) fix target endpoints/core vertices and identify the target parity via bipartiteness; (c) build vertex-disjoint "adjuster" gadgets — small local structures giving a $\pm2$ (or more generally $\pm c$) length choice — chained along a backbone connecting path; (d) use robustness to guarantee each gadget can be built while avoiding everything built so far. This is the concrete mechanism behind three separate 2020 resolutions in one paper (odd-cycle problem, power-of-2 cycles, Thomassen's conjecture) and is flagged in this wiki, on Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often, as "a general-purpose embedding hammer rather than a bespoke trick." See also Liu's own survey, "Sublinear Expanders and Their Applications," *Surveys in Combinatorics* 2024 (a different author, Shoham Letzter, also published a survey of the same title/topic, arXiv:2401.10865 — cross-check both before a fresh attempt), for the wider toolkit (clique subdivisions, minors, immersions, Hamiltonicity results) built on the same base primitive.

Related

- Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — infinite chromatic number $\Rightarrow$ cycle of length $2^n$ infinitely often; PROVED, via de Bruijn–Erdős compactness (reduces to finite average degree) + this theorem directly. - Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — Erdős–Gyárfás power-of-2-cycle conjecture; settled once (average) degree exceeds an absolute constant by this theorem's Corollary 1.3; the tight minimum-degree-$\ge3$ case remains open — this technique does not reach that regime because it needs degree $\ge d_0$ for an unspecified but large absolute constant $d_0$, not degree $\ge3$. - Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) — Erdős–Hajnal $\sum 1/a_i\gg\log k$ conjecture; the sharp constant $\tfrac12$ comes directly from this theorem's density-in-$[\log^8\ell,\ell]$ interval, improving Gyárfás–Komlós–Szemerédi's original 1984 tree-branching proof (documented as Technique 1 on that page; this page is "Technique 2," the modern expander route). - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao), R-spread set families (ALWZ/Rao's central reduction device) — unrelated technique families in this wiki that share the *shape* of "convert a hard extremal question into a tractable pseudorandomness/local-surgery question," useful as a cross-pattern reference when deciding which reduction style fits a new problem. - Komlós & Szemerédi, "On the size of separators in graphs," *Random Structures & Algorithms* 5 (1994) / "Topological cliques in graphs II," *Combin. Probab. Comput.* 5 (1996) — origin of (non-robust) sublinear expanders, the base existence theorem this whole line depends on. - Haslegrave, Kim & Liu, "Extremal density for sparse minors and subdivisions," *Int. Math. Res. Not.* 2022, 15505–15548 — introduces the *robust* sublinear expander used for the harder simultaneous-gadget constructions in Liu–Montgomery's proof. - Shoham Letzter, "Sublinear expanders and their applications," *Surveys in Combinatorics* 2024, arXiv:2401.10865 — broad survey of the whole toolkit (subdivisions, minors, immersions, Hamiltonicity, rainbow/tight cycles) built on the same sublinear-expander primitive; good first stop before adapting this technique to a new target problem.