A mathematical preprint has constructed an infinite family of simple, exactly regular expanding graphs whose longest cycles cover less than a chosen fraction of all vertices. The result supplies counterexamples to the idea that regularity and sublinear expansion alone must force Hamiltonicity — the existence of a cycle that visits every vertex.
The objects under study are finite graphs constructed mathematically for infinitely many integer pairs of degree and size, rather than observations from an empirical population. The authors interpret the construction as a strong disproof of the targeted Hamiltonicity conjecture, while leaving open the positive question of when expansion and degree are enough to guarantee a Hamiltonian cycle.
A regular graph with a built-in limit
The theorem works with fixed parameters satisfying 0 < η < 1/2 and 0 < ε2 < 1/20. It states that there is a positive choice of ε0, depending on η and ε2, such that for any fixed 0 < ε1 < ε0, the construction produces a d-regular graph on n vertices for infinitely many integer pairs (d,n).
Those graphs meet the paper’s sublinear-expansion condition: in the paper’s notation, they are (ε1, ε2 d)-expanders. In ordinary terms, the graph retains the required form of expansion as its size grows, even though its cycles are sharply restricted.
At the same time, the circumference — the length of the longest cycle in the graph — is less than ηn. Because η is chosen below one-half, the longest cycle reaches less than half of the graph’s vertices in this stated family. That rules out a Hamiltonian cycle, which would have to include every vertex.
The degree is on a logarithmic-square scale: the theorem gives an asymptotic relation whose leading factor is one-half multiplying log² n, with an asymptotic term that becomes negligible in the stated limit. The supplied analysis gives no explicit finite-size error bound, so the result identifies a scale rather than a ready-made numerical cutoff for graphs of a particular size.
How the obstruction is built
The graphs are assembled from a biregular Ramanujan graph on two sides, labelled L and S. Each vertex on the L side is replaced by an almost-complete block of d+1 vertices equipped with ports. The S side is left independent, meaning that no edges are placed between its vertices.
The replacement creates two contrasting features. The almost-complete blocks provide dense local structure, while the independent side supplies a sparse separator between them. Ramanujan spectral mixing is then used to certify expansion for sets that combine parts of blocks with vertices from the separator side.
The resulting graph is simple and exactly d-regular. Its order — the total number of vertices — is given by |V(G)| = m(d+1+β), where the expression records the number of base-side blocks together with the block and separator contributions in the construction.
The proof checks expansion across arbitrary vertex subsets rather than testing a selected collection of examples. A base-graph expansion lemma supplies the bound |N_B(A)| ≥ α min{d|A|,m} for every subset A of L, and the remaining verification reduces the required graph-level estimate to |N_G(X)| ≥ δm.
The separator controls the longest cycle
The short-cycle conclusion comes from the independent side of the construction. If the vertices from S that lie on a cycle are deleted, the remaining pieces of that cycle become paths confined to individual blocks. As a result, one cycle can visit at most |S| blocks.
That separation mechanism is the key tension in the example. Expansion gives vertex sets many neighbours in the required sense, but the way those connections pass through the independent side prevents a single cycle from threading through enough blocks to cover the graph. The circumference bound is therefore a structural consequence of the construction.
The authors’ interpretation is deliberately narrower than a claim about all expanding regular graphs. They regard the exponent 2 in the logarithmic-square degree scale as intrinsic to this block–separator construction, while explicitly not claiming that it is intrinsic to the underlying Hamiltonicity problem.
A threshold question remains
By producing this family, the paper shows that the stated combination of regularity and expansion does not automatically produce a Hamiltonian cycle at the targeted scale. It does not establish a universal Hamiltonicity threshold or resolve the positive-side problem of finding conditions that force such a cycle.
The paper leaves open whether, for every ε > 0, there is a constant C(ε) such that every sufficiently large n-vertex d-regular (ε,d)-expander with d ≥ C log² n is Hamiltonian. In other words, the existence of this obstruction does not answer whether a sufficiently larger multiple of log² n could restore the guarantee.
The theorem is stated for infinitely many parameter pairs, and its constants and circumference bound depend on the chosen parameters. The supplied analysis does not provide a concrete numeric threshold for the phrase “sufficiently large d,” so the result cannot by itself be read as a finite-size rule for every graph.
A result still under review
The document is an arXiv version 1 manuscript in math.CO dated 20 Aug 2026, and no journal is listed in the supplied metadata. It is therefore a preprint reporting a proof-based mathematical result.
The authors disclose using ChatGPT 5.6 to check technical details while verifying the sublinear-expansion property and to improve the manuscript’s language. The paper’s central evidence remains the stated graph construction and its proof-based expansion and circumference results.
The funding statement says that all authors are supported by IBS-R029-C4, with Fan Yang also receiving support from the Natural Science Foundation of China, the Natural Science Foundation of Shandong Province, and the China Scholarship Council.
Paper data and sources
Original title: Small circumference in regular sublinear expanders
Authors: Yaobin Chen, Hong Liu, Xin Wei, Fan Yang
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text