Regular graph expanders do not necessarily contain a cycle that reaches most of their vertices. A mathematical preprint constructs regular KS expanders whose longest cycle is shorter than any prescribed fixed fraction of the graph, as long as that fraction is below one-half and the stated parameter conditions hold. The construction works at a degree scale that grows like the square of the logarithm of the number of vertices.
This is a construction result, not an observational finding. The objects under study are explicit graph constructions with dense blocks separated by a sparse vertex set, rather than an observational sample. The paper compares them with questions about Hamilton cycles and long cycles.
A separator sets the ceiling
The first family uses a block-separator design. One side of a biregular Ramanujan graph is blown up into almost-complete blocks, while the other side is kept as an independent sparse separator. The resulting graph is regular and satisfies the KS expansion condition used in the theorem.
The separator also controls every cycle. Once separator vertices are removed from a cycle, what remains is a collection of paths inside individual blocks. Since the cycle can visit no more blocks than there are separator vertices, its length is bounded by the construction's block-separator ratio. The authors choose parameters so that this ratio falls below the target fraction.
That is why the result concerns circumference, the length of the longest cycle, rather than just a single cycle found by the proof. For each fixed target below one-half, the construction gives a regular KS expander whose circumference stays below that target fraction of the graph. The paper says this block-separator obstruction is tied to the logarithmic-square degree regime and cannot support a substantially larger degree.
A second construction uses dense lobes
The second family uses dense lobes attached to an expanding core. An almost-complete lobe is attached to each vertex of a regular expanding core. The proof says every cycle lies either inside the core or inside one lobe together with its core vertex. That prevents a single cycle from combining vertices from many lobes.
These graphs are regular edge expanders. For every sufficiently small edge-expansion parameter, the paper gives an infinite family whose degree grows on the order of the inverse of that parameter, while the circumference grows only on the order of the parameter times the number of vertices. The authors describe this as matching the stated lower-bound scale.
The robust-expander question remains open
The examples stop short of the robust-expander question. The paper reports that both constructions fail the robust-expander condition for structural reasons: a whole block in the first family has only on the order of the degree in outgoing edges, while a lobe in the second has just one external neighbor. The results therefore establish small circumference for the two expansion settings they target, but not for regular robust expanders.
That leaves several questions open. Must sufficiently large regular KS expanders at the logarithmic-square degree scale contain a Hamilton cycle, or at least a cycle covering a fixed positive fraction of the vertices? And can regular robust expanders have a longest cycle whose share of the graph tends to zero, including at the logarithmic-square degree scale? The paper also says the first construction does not apply at substantially larger degrees.
A result built from constructions and proofs
The evidence comes from explicit graph constructions and asymptotic proof arguments, not observations. The expansion arguments use the discrete Cheeger inequality and the expander mixing lemma for biregular bipartite graphs. The document identifies itself as arXiv preprint version 2, dated 18 September 2026.
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