Cycle-length spectrum C(G) of a graph as the core combinatorial object

Statement

For a graph $G$, the cycle spectrum (also "cycle-length set" or "set of cycle lengths") is $$ C(G) \;=\; \{\, \ell \in \mathbb N : G \text{ contains a cycle of length } \ell \,\}. $$ This one set is the shared combinatorial object underneath a whole family of Erdős-style questions — not "does $G$ have a cycle of length exactly $\ell$" in isolation, but *how large, how dense, how spread-out, or how reciprocally-summed* $C(G)$ must be as a function of a global graph parameter (minimum/average degree $d$, girth $g$, chromatic number $k$, connectivity $\kappa$, edge count $m$). Per Bucić–Gishboliner–Sudakov (arXiv:2104.07633, §1): *"Pancyclicity is just an instance of a wider class of problems, which study the properties of the set of cycle lengths of a graph with connection to other graph parameters. The set of cycle lengths of $G$ is called its cycle spectrum, and denoted $C(G)$."*

Named regimes for $C(G)$, from strongest to weakest, all appearing in the Erdős literature: - Pancyclic: $C(G) \supseteq \{3,4,\dots,n\}$ (every length from 3 up to $|V(G)|$) — Bondy, 1971. - Weakly pancyclic: $C(G) \supseteq \{g(G), g(G)+1,\dots,c(G)\}$, every length between the girth and the circumference (longest-cycle length). - Interval-dense / "wide window": $C(G)$ contains every (even, or every, or every-of-one-parity) integer in some explicit interval $[A,B]$ with $B/A$ large — the form produced by Liu–Montgomery-style expander embedding, see Large min/average degree forces a wide interval of cycle lengths (Liu–Montgomery robust-expander embedding). - Large cardinality only: $|C(G)|$ is large, with no control over *where* the lengths lie (the Jacobson–Lehel / Bucić–Gishboliner–Sudakov regime below). - Reciprocal-sum / harmonic: $\sum_{\ell\in C(G)} 1/\ell$ is large — the Erdős–Hajnal / Gyárfás–Komlós–Szemerédi form, see Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree). - Congruence-restricted spectrum: results about $C(G)$ intersected with a fixed residue class, e.g. "contains a cycle of length $\equiv r \pmod m$" or avoiding one prescribed sequence entirely (the Erdős–Gyárfás power-of-2 problem, Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle).

Key extremal theorems fixing the shape of $C(G)$ as a function of a parameter

1. Girth/average-degree lower bound (Erdős's conjecture, proved by Sudakov–Verstraëte 2008). If $G$ has average degree $d$ and girth $g$, then $|C(G)| = \Omega\!\big(d^{\lfloor (g-1)/2\rfloor}\big)$ — WebSearch-corroborated via arXiv:0707.2117 "Cycle lengths in sparse graphs" (Sudakov–Verstraëte), which also strengthens this to $k\lfloor(g-1)/2\rfloor$ *consecutive even* cycle lengths once average degree $\ge 192(k+1)$. The $g=5$ case was settled earlier by Erdős, Faudree, Rousseau & Schelp. Tight: Moore graphs of girth $g$ have about that many vertices, so no better bound is possible in general. 2. Cardinality lower bound for Hamiltonian graphs of bounded minimum degree (Jacobson–Lehel 1999 conjecture, resolved asymptotically by Bucić–Gishboliner–Sudakov 2021/2022, arXiv:2104.07633, Theorem 2). If $G$ is Hamiltonian on $n$ vertices with $\delta(G)\ge3$, then $|C(G)| \ge n^{1-o(1)}$ — resolving both Jacobson–Lehel's $k$-regular conjecture and Verstraëte's minimum-degree-3 strengthening (their "Conjecture 1"). Prior state of the art (Gould–Jacobson–Pfender and others, over roughly two decades) was only $|C(G)|=\Omega(\sqrt n)$; for the weaker *average*-degree-3 hypothesis, Milans–Pfender–Rautenbach–Regen–West show $|C(G)|\ge(1-o(1))\sqrt{m-n}$ and that this is tight — so the regularity/min-degree assumption is what buys the jump from $\sqrt n$ to $n^{1-o(1)}$. 3. Interval/gap-forcing for large min/average degree or chromatic number (Liu–Montgomery 2020). See the dedicated page Large min/average degree forces a wide interval of cycle lengths (Liu–Montgomery robust-expander embedding) — average degree $d\Rightarrow C(G)\supseteq$ every even integer in $[\log^8\ell,\ell]$ for some $\ell\gtrsim d/\log^{12}d$; chromatic number $k\Rightarrow$ analogous odd-length interval; both feed the sharp reciprocal-sum constant $\tfrac12\log k$ on Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree). 4. Long even-cycle interval for linear minimum degree (Gould, Haxell & Scott). If $\delta(G)\ge cn$, then $G$ contains a cycle of every even length between $4$ and $ec(G)-K$, where $ec(G)$ is the length of the longest even cycle and $K=K(c)$ is an absolute constant — cited in Bucić–Gishboliner–Sudakov §1 as a companion "interval-type" result to their own cardinality-only theorem. 5. Pancyclicity from Hamiltonicity-forcing conditions (Bondy's 1973 "meta-conjecture"). *"Any non-trivial condition which guarantees the existence of a Hamilton cycle should also guarantee that the given graph is pancyclic, with possibly a simple family of exceptions."* Confirmed instance-by-instance: Bondy himself showed Ore's condition ($\sigma_2(G)\ge n$) $\Rightarrow$ pancyclic or $G=K_{n/2,n/2}$; Bauer–Schmeichel extended this (building on Schmeichel–Hakimi) to the Bondy, Chvátal, and Fan Hamiltonicity conditions; the Jackson–Ordaz conjecture ($\kappa(G)>\alpha(G)\Rightarrow$ pancyclic, strengthening Chvátal–Erdős's Hamiltonicity theorem) has an approximate proof by Keevash–Sudakov ($\kappa(G)\ge600\,\alpha(G)$ suffices). 6. Congruence and unified conjectures (Gao, Huo, Liu & Ma, 2022, IMRN). A single paper confirms several previously-separate conjectures on $C(G)$ relative to minimum degree, connectivity, and chromatic number (including conjectures of Liu–Ma 2018, Thomassen 1983, and Dean 1988) — evidence that $C(G)$-shaped questions cluster into a provably-unifiable family rather than needing one bespoke argument each.

Facts

- Extremal near-tight construction for the cardinality question: for $k$-regular Hamiltonian $G$, Jacobson–Lehel's necklace of $n/2k$ copies of $K_{k,k}$ (each missing one edge, chained in a cycle) realizes *only* the even lengths in $[4,2k]\cup[2n/k,n]$, giving $|C(G)| = \tfrac n2\cdot\tfrac{k-2}{k}+k$ — this is the matching upper-bound construction the $n^{1-o(1)}$ theorem is asymptotically chasing (still an open gap: $n^{1-o(1)}$ vs. the conjectured tight $\Omega(n)$). - Regularity vs. minimum degree matters structurally, not just cosmetically. Analogous to Thomassen's large-girth-subgraph conjecture (open even for girth 7 in the minimum-degree setting but easy for regular graphs), the cycle-spectrum-cardinality question is "easy" reduced to average degree (tight $\sqrt{m-n}$ bound) but was open at $n^{1-o(1)}$ for 20+ years once posed with the min-degree-3 hypothesis instead of regularity — a recurring pattern flagged explicitly in Bucić–Gishboliner–Sudakov §1 with the Entringer–Swart / Smith second-Hamilton-cycle example as another instance of the same phenomenon. - The proof of the $n^{1-o(1)}$ theorem is constructive, giving a polynomial-time algorithm to *find* the $n^{1-o(1)}$ distinct cycle lengths given a specified Hamilton cycle — not just an existence proof. - Two structurally different "grow $C(G)$" toolkits coexist and solve different sub-regimes: (a) sublinear-expander embedding (Large min/average degree forces a wide interval of cycle lengths (Liu–Montgomery robust-expander embedding)) gives *interval density* (every length in a range) but needs the input parameter (average degree, or chromatic number) to be large in an absolute sense; (b) the Bucić–Gishboliner–Sudakov chord-interlacing/parallel-family method (below, under Technique) gives *cardinality* ($n^{1-o(1)}$ distinct lengths, no control over which lengths) but works down at the *constant* minimum-degree-3 floor, the weakest possible non-trivial hypothesis (min degree $\ge3$; min degree 2 trivially caps $|C(G)|=1$). - The girth-driven bound is a genuinely different regime: girth $g$ forces $C(G)$'s *cardinality* to scale as $d^{\lfloor(g-1)/2\rfloor}$ rather than linearly in $n$ or $d$ — because large girth forbids short cycles outright, the "many distinct lengths" question there is really a "long cycle exists and induces many lengths via detours" question, tight against Moore-graph-type constructions.

Technique

When to reach for "study $C(G)$ directly" as a problem template. Any Erdős-style question of the shape *"a global graph parameter (min/avg degree, girth, chromatic number, connectivity) forces [a specific cycle length / pancyclicity / a whole interval of lengths / many distinct lengths / a large reciprocal sum]"* is an instance of bounding some functional of $C(G)$. Recognizing this lets you import whichever of the toolkits above matches the *shape* of the target conclusion:

- Target is "$C(G)$ contains a specific value or a whole residue class / power sequence" → reach for Large min/average degree forces a wide interval of cycle lengths (Liu–Montgomery robust-expander embedding) (sublinear-expander adjuster gadgets), the tool that resolved 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 partially, and the chromatic-number sibling of Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree). - Target is "$|C(G)|$ is large" with no constraint on which lengths → reach for the Bucić–Gishboliner–Sudakov chord-splitting method, sketched next. - Target is "$\sum_{\ell\in C(G)}1/\ell$ is large" → reach for the dyadic/geometric-scale harmonic-summation trick (density-in-$[A,B]\Rightarrow\Theta(\log(B/A))$ reciprocal sum), documented on Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) as "Technique 1." - Target is girth-parametrized ($g$ fixed or growing, want $|C(G)|$ or long-cycle bounds in terms of average degree $d$) → reach for Sudakov–Verstraëte's sparse-graph cycle-length methods (arXiv:0707.2117). - Target is "Hamiltonicity-forcing condition $\Rightarrow$ pancyclic" → treat it as a Bondy-meta-conjecture instance: check whether the specific sufficient condition (Ore, Chvátal, Fan, Chvátal–Erdős, …) has already been shown pancyclic-implying (Bondy, Bauer–Schmeichel, Keevash–Sudakov) or is a fresh case of the same meta-pattern.

**The Bucić–Gishboliner–Sudakov cardinality method, step by step (arXiv:2104.07633, §2 sketch) — the key *reusable* recombination move for "many distinct cycle lengths, don't care which":**

1. Split the Hamilton cycle into a hierarchy of $k\approx\sqrt{\log n}$ "section-pairs" (pairs of disjoint sub-paths of the cycle), arranged so each pair has $n^{1-o(1)}$ chords between its two sections. 2. Within one section-pair, use the Erdős–Szekeres lemma (their Lemma 3) on chords: any large enough family of vertex-disjoint chords between two paths contains a large sub-family that is either entirely parallel or entirely interlacing (crossing) — a Ramsey-type dichotomy on the combinatorial order type of chord endpoints. 3. Exploit each case for a different length-control property. An interlacing family of chords, combined with cycle sections between consecutive chords, produces many paths whose lengths are *clustered in a narrow window* (differences $O(n^\varepsilon)$); a suitably-selected "spread" sub-family (via a maximal-distance greedy choice) instead produces paths whose lengths are *far apart* (differences $\Theta(n^\varepsilon)$ or more). 4. Combine a "clustered" set of $\Omega(n^\varepsilon)$ lengths from one section-pair with a "spread" set of $\Omega(n^\varepsilon)$ lengths from another section-pair by concatenation: if $Q_1,\dots,Q_k$ (lengths in a window of width $n^\varepsilon$) and $R_1,\dots,R_\ell$ (lengths pairwise $>n^\varepsilon$ apart) come from vertex-disjoint parts of the graph, then all $k\ell$ sums $|Q_i|+|R_j|$ are automatically distinct (the "fill-in-the-gaps" trick: clustered lengths fill in the fine detail between coarsely-spread lengths, and no collision is possible because the spread part dominates over the clustered part's window). This single combinatorial fact converts two separate $\Omega(\sqrt n)$-sized length-sets into one $\Omega(n)$-sized distinct-length set. 5. Iterate the clustered/spread construction across $\sqrt{\log n}/\log\log n$ nested section-pairs, each iteration multiplying the running count of distinct lengths by another $n^\varepsilon$ factor (at the cost of a polylogarithmic loss per step) — after all iterations, this compounds to $n^{1-o(1)}$ distinct lengths overall. 6. A technical prerequisite: if the Hamilton cycle's chord structure resists a clean two-piece split (e.g. only "diameter" chords are present), first *reroute* the cycle using two well-chosen chords plus large arcs of the original cycle, producing a new Hamilton cycle that does admit the needed split.

Why it works (core intuition, for recombination). The method never tries to *directly* engineer a cycle of a target length (that is the harder, more rigid embedding problem solved by expander-adjuster methods). Instead it exploits a purely order-theoretic dichotomy (Erdős–Szekeres: any long sequence has a long monotone or long "crossing" subsequence) to *guarantee* that some sub-family of chords must behave coherently — either bunching lengths into a tight cluster or spreading them into a well-separated set — and then uses elementary additive-distinctness (sumset non-collision when one part's spread dominates the other's window) to multiply small distinct-length counts into much larger ones. This decouples "produce many distinct numbers" from "produce numbers with any specific value," which is exactly the right relaxation for a *cardinality-only* target, and is why the technique reaches all the way down to the minimum (not average) degree-3 floor where expander methods (needing large *absolute* degree) do not apply.

Recombination hooks. (a) Whenever a target problem's conclusion is phrased as "$|C(G)|$ is large" (as opposed to "$C(G)$ contains value $v$" or "$C(G)\supseteq[A,B]$"), first check whether a clustered-vs-spread chord dichotomy argument can be built on whatever Hamiltonian/near-Hamiltonian backbone the problem provides — this is a fundamentally different (and often easier, since it needs no expansion/degree lower bound beyond minimum degree 3) route than embedding-based methods. (b) The Erdős–Szekeres monotone/crossing dichotomy on chords is itself a transferable primitive, usable any time "many disjoint objects with two endpoints on a fixed linear order" arise (interval scheduling, crossing-number arguments, permutation pattern problems) and one wants a large coherent (parallel or interlacing) sub-family for free. (c) When a new Erdős problem's statement mentions "the set of cycle lengths" or "cycle spectrum" explicitly, first classify which of the five regimes above (pancyclic / weakly-pancyclic / interval-dense / cardinality / reciprocal-sum / congruence-restricted) it is asking about — the classification alone usually identifies which of the (at least) three independently-developed toolkits (sublinear expanders, chord clustered/spread splitting, girth-driven sparse-graph methods) is the right one to try first.

Related

- Large min/average degree forces a wide interval of cycle lengths (Liu–Montgomery robust-expander embedding) — the Liu–Montgomery sublinear-expander machinery; the *interval-density* branch of $C(G)$-control, sibling to this page's *cardinality* branch. - Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — infinite chromatic number $\Rightarrow$ cycle of length $2^n$ infinitely often; a "specific value in $C(G)$" instance. - Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — Erdős–Gyárfás power-of-2-cycle conjecture (min degree $\ge3$); a "specific value/congruence-restricted" instance, still open in the tight min-degree-3 regime. - Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) — Erdős–Hajnal $\sum_{\ell\in C(G)}1/\ell \gg\log k$; the reciprocal-sum branch, with two independent proof techniques recorded there. - Liu–Montgomery (2020/2023) — Erdős–Hajnal odd-cycle reciprocal-sum problem, Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs, Carr — any minimal Erdős–Gyárfás counterexample is predominantly cubic, Erdős–Gyárfás conjecture confirmed for 3-connected cubic planar graphs (Heckman–Krakovski 2013), Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02) — cluster of pages on the Erdős–Gyárfás power-of-2 conjecture and partial results, all instances of "does $C(G)$ contain a value from a prescribed sequence." - Bucić, Gishboliner & Sudakov, "Cycles of many lengths in Hamiltonian graphs," *Forum of Mathematics, Sigma* 10 (2022), E70, arXiv:2104.07633 — resolves the Jacobson–Lehel (1999) / Verstraëte cardinality conjecture asymptotically ($|C(G)|\ge n^{1-o(1)}$ for Hamiltonian $\delta(G)\ge3$); source of the clustered/spread chord-splitting technique documented above. - Sudakov & Verstraëte, "Cycle lengths in sparse graphs," arXiv:0707.2117 (journal version "Cycle lengths and minimum degree of graphs," *J. Combin. Theory Ser. B*) — proves Erdős's girth/average-degree conjecture $|C(G)|=\Omega(d^{\lfloor(g-1)/2\rfloor})$ and its consecutive-even-lengths strengthening. - Bondy, "Pancyclic graphs I," *J. Combin. Theory Ser. B* 11 (1971) 80–84, and the 1973 "meta-conjecture" — founding statement of the Hamiltonicity-condition-implies-pancyclicity pattern. - Gould, Haxell & Scott — long-even-cycle interval theorem for linear minimum degree, cited as a companion interval-type result in Bucić–Gishboliner–Sudakov §1. - Gao, Huo, Liu & Ma, "A unified proof of conjectures on cycle lengths in graphs," *Int. Math. Res. Not.* 2022(10) — resolves several previously separate $C(G)$-vs-(degree/connectivity/chromatic-number) conjectures (Liu–Ma 2018, Thomassen 1983, Dean 1988) in one paper. - Douglas West, "Cycle Spectrum of Hamiltonian Graphs," dwest.web.illinois.edu/regs/specham.html — open-problem-garden page tracking the Jacobson–Lehel minimum-spectrum-size question and successive bound refinements (Gould–Jacobson–Pfender $\Omega(\sqrt n)$; Milans–Rautenbach–Regen–West $\Omega(\sqrt{m-n})$).