arxiv: 2603.08675 · v2 · submitted 2026-03-09 · 🧮 math.CO · math.GR

Recognition: no theorem link

The Lov\'asz conjecture holds for moderately dense Cayley graphs

Benjamin Bedert , Nemanja Dragani\'c , Alp M\"uyesser , Mat\'ias Pavez-Sign\'e

Authors on Pith no claims yet

Pith reviewed 2026-05-15 14:27 UTC · model grok-4.3

classification 🧮 math.CO math.GR MSC 05C4505C25

keywords Cayley graphsHamilton cyclesLovász conjecturearithmetic regularity lemmavertex-transitive graphsHamiltonian graphsgroup theory

0 comments

The pith

There exists an absolute constant c>0 such that every large connected n-vertex Cayley graph with degree d≥n^{1-c} has a Hamilton cycle.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that connected Cayley graphs on n vertices become Hamiltonian as soon as their degree reaches n raised to a power slightly below 1, for some fixed c>0 and all large n. This advances the Lovász conjecture, which asks whether every connected vertex-transitive graph has a Hamilton cycle, by handling a wide class of such graphs at much lower densities than before. Earlier work required the degree to be at least a constant fraction of n. The new proof uses a specialized arithmetic regularity lemma for Cayley graphs instead of the standard regularity lemma. Readers care because it shows the group symmetry in Cayley graphs can be exploited to guarantee cycles under weaker conditions, moving closer to a full resolution of the conjecture.

Core claim

We show that there is an absolute constant c>0 such that every large connected n-vertex Cayley graph with degree d≥n^{1-c} has a Hamilton cycle. This makes progress towards the Lovász conjecture and improves upon the previous best result of this form due to Christofides, Hladký, and Máthé from 2014 concerning graphs with d≥εn. Our proof avoids the use of Szemerédi's regularity lemma and relies instead on an efficient arithmetic regularity lemma specialised to Cayley graphs.

What carries the argument

An efficient arithmetic regularity lemma specialised to Cayley graphs that controls additive structure to locate Hamilton cycles.

If this is right

The Lovász conjecture holds for all sufficiently large connected Cayley graphs above the n^{1-c} degree threshold.
The required density for Hamiltonicity in Cayley graphs improves from linear in n to n raised to a power less than 1.
Arithmetic regularity lemmas can replace Szemerédi's lemma in Hamiltonicity proofs that exploit group structure.
All large Cayley graphs meeting the degree condition are guaranteed to contain a cycle through every vertex.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the arithmetic approach generalizes, similar density thresholds might hold for other families of vertex-transitive graphs.
Any counterexample to the full Lovász conjecture must either be non-Cayley or have degree below n to a power close to 1.
Algorithms that search for Hamilton cycles in explicit Cayley graphs could succeed at lower degrees than previously known.
The same regularity techniques might extend to directed Cayley graphs or Hamilton paths in the same setting.

Load-bearing premise

The arithmetic regularity lemma for Cayley graphs works with constants independent of the underlying group and keeps the degree threshold strictly below linear in n.

What would settle it

A connected Cayley graph on n vertices with degree n^{1-c} for small fixed c that lacks a Hamilton cycle, occurring for arbitrarily large n, would disprove the claim.

Figures

Figures reproduced from arXiv: 2603.08675 by Alp M\"uyesser, Benjamin Bedert, Mat\'ias Pavez-Sign\'e, Nemanja Dragani\'c.

**Figure 1.** Figure 1: A picture of the v-absorber F5 and the corresponding (x0, y0)-paths. until we construct enough absorbers so that they can deal with the leftover after Step 2. Moreover, P has a restriction on how many vertices it can avoid, and so it imposes a restriction on how many absorbers we can construct with this approach. Secondly, the more we rely on property P to connect vertices, the more we might deteriorate th… view at source ↗

**Figure 2.** Figure 2: This picture shows the path 1234 in the auxiliary digraph, which then corresponds to a path of [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

read the original abstract

We show that there is an absolute constant $c>0$ such that every large connected $n$-vertex Cayley graph with degree $d\geq n^{1-c}$ has a Hamilton cycle. This makes progress towards the Lov\'asz conjecture and improves upon the previous best result of this form due to Christofides, Hladk\'y, and M\'ath\'e from 2014 concerning graphs with $d\geq \varepsilon n$. Our proof avoids the use of Szemer\'edi's regularity lemma and relies instead on an efficient arithmetic regularity lemma specialised to Cayley graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper improves the density threshold for Hamilton cycles in Cayley graphs from linear to n^{1-c} via a specialized arithmetic regularity lemma.

read the letter

This paper shows that large connected Cayley graphs on n vertices with degree at least n to a small fixed power have Hamilton cycles. It improves the 2014 Christofides-Hladký-Máthé result, which needed linear density, by swapping the general regularity lemma for an arithmetic version built for Cayley graphs. That is the concrete gain: a quantitative drop in the required degree while keeping the argument structured around an approximation that respects the group action. The abstract is direct about the claim and the tool, and the approach fits the setting because Cayley graphs carry additive structure that a general regularity lemma wastes. The proof sketch avoids the usual tower-type losses from Szemerédi by specializing early, which is a sensible move for this problem. The soft spot is whether the arithmetic lemma really delivers an absolute c without n-dependent blow-up in the number of parts or the approximation error. Even efficient versions of such lemmas can produce parameters that grow with 1/δ when δ drops to n^{-c}, and the cycle-finding step needs the structured pieces to stay dense enough relative to those parts. If the constants hide an extra log n or worse, the claimed absolute c would not hold for all large n. The paper asserts it works, so the specialized lemma must be strong enough on paper, but the bounds would need explicit checking. This is for people tracking the Lovász conjecture or regularity methods in vertex-transitive graphs. A reader who cares about quantitative progress on Hamiltonicity in groups will get a clear step forward. It deserves a serious referee because the improvement is real and the method is targeted, even if the constants need tightening.

Referee Report

0 major / 3 minor

Summary. The paper proves that there exists an absolute constant c > 0 such that every sufficiently large connected n-vertex Cayley graph with degree d ≥ n^{1-c} contains a Hamilton cycle. The argument proceeds by applying an efficient arithmetic regularity lemma specialized to Cayley graphs to obtain a structured approximation of the graph, then constructing a Hamilton cycle within the resulting regularized structure; this avoids the tower-type bounds of Szemerédi's regularity lemma and improves on the linear-density threshold of Christofides-Hladký-Máthé (2014).

Significance. If the quantitative bounds hold as claimed, the result constitutes a substantial advance toward the Lovász conjecture for vertex-transitive graphs, establishing Hamiltonicity for Cayley graphs whose degree is only moderately sublinear. The use of a specialized, efficient arithmetic regularity lemma is a genuine technical strength that sidesteps the n-dependent losses typical of general regularity lemmas and yields an absolute (n-independent) c; this approach may also be adaptable to other problems on Cayley graphs or groups with moderate density.

minor comments (3)

[§1] §1, paragraph following Theorem 1.1: the statement that the arithmetic regularity lemma is 'efficient' should be accompanied by an explicit reference to the precise quantitative bound on the number of atoms (or the dependence of ε on δ) that is invoked later in the proof.
[§3] §3, Lemma 3.2: the error term arising from the regularity approximation is stated as o(1), but the manuscript should record the explicit dependence on the input density δ = d/n to confirm that it remains smaller than the gap needed for the cycle-finding step when δ = n^{-c}.
[Theorem 1.1] The proof of the main theorem assumes the graph is connected; a brief remark on whether the same argument yields a Hamilton path (rather than cycle) in the disconnected case would be useful for completeness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, the recognition of the technical contribution of the efficient arithmetic regularity lemma, and the recommendation for minor revision. The report accurately captures the main result and its improvement over the linear-density threshold of Christofides-Hladký-Máthé (2014).

Circularity Check

0 steps flagged

No circularity: proof relies on external specialized regularity lemma without self-referential reduction

full rationale

The paper's central claim is a theorem asserting an absolute constant c>0 for Hamiltonicity in sufficiently dense Cayley graphs. The derivation invokes an efficient arithmetic regularity lemma specialized to Cayley graphs (cited as external) to obtain a structured approximation, then constructs the cycle on that approximation. No equations in the provided abstract or description reduce the Hamilton cycle existence to a fitted parameter, a self-defined quantity, or a load-bearing self-citation chain. The argument is self-contained once the external lemma is granted, with no renaming of known results or smuggling of ansatzes via prior author work. This matches the default non-circular case for a proof paper using cited external tools.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard group axioms and the existence of an efficient arithmetic regularity lemma for Cayley graphs; no new free parameters or invented entities are introduced in the abstract.

axioms (2)

standard math Basic axioms of finite groups and Cayley graphs (vertex-transitivity, left/right multiplication)
Invoked implicitly when defining the graphs and stating connectivity.
domain assumption Existence of an efficient arithmetic regularity lemma specialized to Cayley graphs
The proof replaces Szemerédi regularity with this tool; the abstract treats it as available.

pith-pipeline@v0.9.0 · 5407 in / 1296 out tokens · 25720 ms · 2026-05-15T14:27:00.964266+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

[1]

Random Cayley graphs and expanders.Random Structures & Algorithms, 5(2):271–284, 1994

Noga Alon and Yuval Roichman. Random Cayley graphs and expanders.Random Structures & Algorithms, 5(2):271–284, 1994

work page 1994
[2]

Decomposition into cycles I: Hamilton decompositions

Brian Alspach, Jean-Claude Bermond, and Dominique Sotteau. Decomposition into cycles I: Hamilton decompositions. InCycles and rays, pages 9–18. Springer, 1990

work page 1990
[3]

Automorphism groups, isomorphism, reconstruction.North-Holland–Elsevier, pages 1447– 1540, 1995

Laszlo Babai. Automorphism groups, isomorphism, reconstruction.North-Holland–Elsevier, pages 1447– 1540, 1995

work page 1995
[4]

On Graham’s rearrangement conjecture overF n 2 .arXiv preprint arXiv:2508.18254, 2025

Benjamin Bedert, Matija Buci´ c, Noah Kravitz, Richard Montgomery, and Alp M¨ uyesser. On Graham’s rearrangement conjecture overF n 2 .arXiv preprint arXiv:2508.18254, 2025

work page arXiv 2025
[5]

Vertex-transitive graphs that have no Hamilton decomposition.Journal of Combinatorial Theory, Series B, 114:237–246, 2015

Darryn Bryant and Matthew Dean. Vertex-transitive graphs that have no Hamilton decomposition.Journal of Combinatorial Theory, Series B, 114:237–246, 2015. 15

work page 2015
[6]

Towards Graham’s rearrangement conjecture via rainbow paths.arXiv preprint 2503.01825, 2025

Matija Buci´ c, Bryce Frederickson, Alp M¨ uyesser, Alexey Pokrovskiy, and Liana Yepremyan. Towards Graham’s rearrangement conjecture via rainbow paths.arXiv preprint 2503.01825, 2025

work page arXiv 2025
[7]

Long cycles in vertex transitive digraphs.arXiv preprint arXiv:2602.16333, 2026

Matija Buci´ c, Kevin Hendrey, Bojan Mohar, Raphael Steiner, and Liana Yepremyan. Long cycles in vertex transitive digraphs.arXiv preprint arXiv:2602.16333, 2026

work page arXiv 2026
[8]

Hamilton cycles in dense vertex-transitive graphs

Demetres Christofides, Jan Hladk` y, and Andr´ as M´ ath´ e. Hamilton cycles in dense vertex-transitive graphs. Journal of Combinatorial Theory, Series B, 109:34–72, 2014

work page 2014
[9]

Cycle- factors of regular graphs via entropy.arXiv preprint arXiv:2507.19417, 2025

Micha Christoph, Nemanja Dragani´ c, Ant´ onio Gir˜ ao, Eoin Hurley, Lukas Michel, and Alp M¨ uyesser. Cycle- factors of regular graphs via entropy.arXiv preprint arXiv:2507.19417, 2025

work page arXiv 2025
[10]

New bounds for linear arboricity and related problems.arXiv preprint arXiv:2507.20500, 2025

Micha Christoph, Nemanja Dragani´ c, Ant´ onio Gir˜ ao, Eoin Hurley, Lukas Michel, and Alp M¨ uyesser. New bounds for linear arboricity and related problems.arXiv preprint arXiv:2507.20500, 2025

work page arXiv 2025
[11]

Hamiltonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

Nemanja Dragani´ c, Richard Montgomery, David Munh´ a Correia, Alexey Pokrovskiy, and Benny Sudakov. Hamiltonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

work page arXiv 2024
[12]

The minimal regular graph containing a given graph.The American Mathe- matical Monthly, 70:1074–1075, 1963

Paul Erd˝ os and Paul Kelly. The minimal regular graph containing a given graph.The American Mathe- matical Monthly, 70:1074–1075, 1963

work page 1963
[13]

Perfect matchings in random subgraphs of regular bipartite graphs.Journal of Graph Theory, 97(2):208–231, 2021

Roman Glebov, Zur Luria, and Michael Simkin. Perfect matchings in random subgraphs of regular bipartite graphs.Journal of Graph Theory, 97(2):208–231, 2021

work page 2021
[14]

Hamilton cycles in pseudorandom graphs

Stefan Glock, David Munh´ a Correia, and Benny Sudakov. Hamilton cycles in pseudorandom graphs. Advances in Mathematics, 458:109984, 2024

work page 2024
[15]

Springer Science & Business Media, 2013

Chris Godsil and Gordon F Royle.Algebraic graph theory. Springer Science & Business Media, 2013

work page 2013
[16]

Perfect matchings ino(nlogn) time in regular bipartite graphs

Ashish Goel, Michael Kapralov, and Sanjeev Khanna. Perfect matchings ino(nlogn) time in regular bipartite graphs. InProceedings of the Forty-second ACM Symposium on Theory of Computing, pages 39–46, 2010

work page 2010
[17]

Perfect matchings ino(n 1.5) time in regular bipartite graphs.Combinatorica, 39(2):323–354, 2019

Ashish Goel, Michael Kapralov, and Sanjeev Khanna. Perfect matchings ino(n 1.5) time in regular bipartite graphs.Combinatorica, 39(2):323–354, 2019

work page 2019
[18]

Inducing regulation of any digraphs.Discrete applied mathematics, 157(5):947–952, 2009

Joanna G´ orska and Zdzis/suppress law Skupie´ n. Inducing regulation of any digraphs.Discrete applied mathematics, 157(5):947–952, 2009

work page 2009
[19]

A Szemer´ edi-type regularity lemma in abelian groups, with applications.Geometric & Func- tional Analysis GAF A, 15(2):340–376, 2005

Ben Green. A Szemer´ edi-type regularity lemma in abelian groups, with applications.Geometric & Func- tional Analysis GAF A, 15(2):340–376, 2005

work page 2005
[20]

Longest cycles in vertex-transitive and highly connected graphs.Bulletin of the London Mathematical Society, 57(10):2975–2990, 2025

Carla Groenland, Sean Longbrake, Raphael Steiner, J´ er´ emie Turcotte, and Liana Yepremyan. Longest cycles in vertex-transitive and highly connected graphs.Bulletin of the London Mathematical Society, 57(10):2975–2990, 2025

work page 2025
[21]

Wiley-Interscience, 2000

Svante Janson, Tomasz /suppress Luczak, and Andrzej Ruci´ nski.Random graphs. Wiley-Interscience, 2000

work page 2000
[22]

Using randomized sparsification to approximate minimum cuts

David R Karger. Using randomized sparsification to approximate minimum cuts. InSODA, volume 94, pages 424–432, 1994

work page 1994
[23]

Karp.Reducibility among Combinatorial Problems, pages 85–103

Richard M. Karp.Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972

work page 1972
[24]

The robust component structure of dense regular graphs and applications.Proceedings of the London Mathematical Society, 110(1):19–56, 2015

Daniela K¨ uhn, Allan Lo, Deryk Osthus, and Katherine Staden. The robust component structure of dense regular graphs and applications.Proceedings of the London Mathematical Society, 110(1):19–56, 2015

work page 2015
[25]

Hamilton decompositions of regular expanders: applications.Journal of Combinatorial Theory, Series B, 104:1–27, 2014

Daniela K¨ uhn and Deryk Osthus. Hamilton decompositions of regular expanders: applications.Journal of Combinatorial Theory, Series B, 104:1–27, 2014

work page 2014
[26]

Hamiltonian degree sequences in digraphs.Journal of Combinatorial Theory, Series B, 100(4):367–380, 2010

Daniela K¨ uhn, Deryk Osthus, and Andrew Treglown. Hamiltonian degree sequences in digraphs.Journal of Combinatorial Theory, Series B, 100(4):367–380, 2010. 16

work page 2010
[27]

Hamilton cycles and paths in vertex-transitive graphs—current directions.Discrete mathematics, 309(17):5491–5500, 2009

Klavdija Kutnar and Dragan Maruˇ siˇ c. Hamilton cycles and paths in vertex-transitive graphs—current directions.Discrete mathematics, 309(17):5491–5500, 2009

work page 2009
[28]

Hamilton cycles in sparse robustly expanding digraphs.Electronic Journal of Combinatorics, 25(3):Article P3.44, 2018

Allan Lo and Viresh Patel. Hamilton cycles in sparse robustly expanding digraphs.Electronic Journal of Combinatorics, 25(3):Article P3.44, 2018

work page 2018
[29]

Problem 11

L´ aszl´ o Lov´ asz. Problem 11. InCombinatorial Structures and Their Applications, page 497. Gordon and Breach, New York, 1970. Proc. Calgary International Conference on Combinatorial Structures and Their Applications, 1969

work page 1970
[30]

Colton Magnant and Daniel M. Martin. A note on the path cover number of regular graphs.Australasian journal of Combinatorics, 43:211–217, 2009

work page 2009
[31]

On the method of bounded differences

Colin McDiarmid. On the method of bounded differences. In J. Siemons, editor,Surveys in Combinatorics, 1989 (Norwich, 1989), volume 141 ofLondon Mathematical Society Lecture Note Series, pages 148–188. Cambridge University Press, Cambridge, 1989

work page 1989
[32]

Spanning trees in random graphs.Advances in Mathematics, 356, 2019

Richard Montgomery. Spanning trees in random graphs.Advances in Mathematics, 356, 2019

work page 2019
[33]

Small hitting sets for longest paths and cycles.Proceedings of the American Mathematical Society, 2026

Sergey Norin, Raphael Steiner, St´ ephan Thomass´ e, and Paul Wollan. Small hitting sets for longest paths and cycles.Proceedings of the American Mathematical Society, 2026

work page 2026
[34]

Hamiltonian paths in Cayley graphs.Discrete Mathematics, 309(17):5501– 5508, 2009

Igor Pak and Radoˇ s Radoiˇ ci´ c. Hamiltonian paths in Cayley graphs.Discrete Mathematics, 309(17):5501– 5508, 2009

work page 2009
[35]

Rapaport-Strasser

E. Rapaport-Strasser. Cayley color groups and hamilton lines.Scripta Math., 24:51–58, 1959

work page 1959
[36]

An approximate Dirac-type theorem for k-uniform hypergraphs.Combinatorica, 28(2):229–260, 2008

Vojtˇ ech R¨ odl, Endre Szemer´ edi, and Andrzej Ruci´ nski. An approximate Dirac-type theorem for k-uniform hypergraphs.Combinatorica, 28(2):229–260, 2008

work page 2008
[37]

When the cartesian product of directed cycles is Hamiltonian.Journal of Graph Theory, 2(2):137–142, 1978

William Trotter and Paul Erd˝ os. When the cartesian product of directed cycles is Hamiltonian.Journal of Graph Theory, 2(2):137–142, 1978. 17

work page 1978