In 1969, László Lovász conjectured that every connected vertex-transitive graph has a Hamiltonian path — a route that visits every vertex exactly once. Vertex-transitive graphs are graphs where every vertex looks the same: the symmetry group acts transitively, so the view from any node is identical to the view from any other. Cayley graphs of finite groups are the canonical examples. The conjecture says that this structural symmetry should guarantee the existence of a path through every vertex.
Fifty-seven years later, the conjecture remains open. But the boundary of what is known keeps moving.
Bedert, Draganić, Müyesser, and Pavez-Signé prove that there exists an absolute constant c > 0 such that every large connected Cayley graph on n vertices with degree at least n^(1-c) contains a Hamiltonian cycle — not just a path but a cycle that returns to its start. The previous best result of this type, from Christofides, Hladký, and Máthé in 2014, required degree at least a linear fraction of n. The new result pushes the threshold down to a sublinear power: instead of needing connections to a constant fraction of all vertices, you need connections to n^(1-c) of them. For large n, this is substantially fewer.
The technical innovation is what does not appear in the proof. Szemerédi's regularity lemma — one of the most powerful and widely used tools in graph theory — is the standard approach for embedding structures in dense graphs. The regularity lemma works by partitioning a graph into pieces that look pseudorandom, then finding structures within the pseudorandom approximation. But the regularity lemma incurs enormous quantitative losses: the partition size involves tower functions, and the error terms are correspondingly large. The authors develop instead an arithmetic regularity lemma specialized to Cayley graphs, exploiting the algebraic structure of the underlying group to obtain tighter bounds.
The through-claim is about the relationship between the right tool and the right structure. The general-purpose regularity lemma works for all graphs but loses quantitative control. The specialized arithmetic regularity lemma works only for Cayley graphs but preserves quantitative control. The Lovász conjecture is specifically about vertex-transitive graphs — graphs with algebraic structure. Using a tool that ignores that structure (the regularity lemma) imposes unnecessary cost. Using a tool that exploits it (arithmetic regularity) lowers the density threshold. The conjecture is about symmetry. The progress came from using a proof technique that respects the symmetry rather than erasing it.