In 1970, László Lovász conjectured that every connected Cayley graph contains a Hamiltonian cycle — a path that visits every vertex exactly once and returns to the start. A Cayley graph is a graph built from a group: vertices are group elements, and edges connect elements that differ by a generator. The algebraic structure of the group determines the graph's connectivity. The conjecture says this structure is always rich enough to guarantee a Hamiltonian cycle.
The conjecture remains open after 55 years. What makes it hard is that Hamiltonian cycle existence is NP-complete in general graphs — there's no efficient algorithm to decide it. Cayley graphs have more structure than arbitrary graphs, but translating algebraic properties (generators, cosets, normal subgroups) into cycle existence has resisted all known techniques.
Bedert, Draganić, Müyesser, and Pavez-Signé (arXiv:2603.08675, March 2026) prove the conjecture for moderately dense Cayley graphs — those with degree at least n^(1−c) for an absolute constant c. The previous best result, from 2014, required degree at least εn — linearly proportional to the number of vertices. The improvement from linear to sublinear density is a qualitative shift, because it includes graphs where most potential edges are absent.
The key move is what they avoided. The standard tool for graph regularity problems is Szemerédi's regularity lemma, which partitions any graph into approximately random-looking pieces. The regularity lemma is universal — it works on any graph — but it's inefficient, requiring partition sizes that are towers of exponentials in the approximation parameter. This inefficiency contaminates every downstream result.
Cayley graphs, because they arise from groups, have algebraic regularity that Szemerédi's combinatorial regularity doesn't exploit. The authors developed an arithmetic regularity lemma specialized to Cayley graphs, replacing the tower-function bounds with polynomial bounds. The algebraic structure — the group operations that define the graph — makes the regularity problem fundamentally easier than in the general case.
The result is not about discovering new structure in Cayley graphs. The algebraic regularity was always there. It's about building a tool that sees it. Szemerédi's lemma treats a Cayley graph as if it were an arbitrary graph, discarding the information that the vertices are group elements. The arithmetic regularity lemma preserves that information, and the preservation is what makes the theorem possible.
Bedert, Draganić, Müyesser, and Pavez-Signé, "The Lovász conjecture holds for moderately dense Cayley graphs," arXiv:2603.08675 (March 2026).