The Lovász conjecture holds for moderately dense Cayley graphs

Benjamin Bedert, Nemanja Draganić, Alp Müyesser, Matías Pavez-Signé · 2026

Read The Lovász conjecture holds for moderately dense Cayley graphs by Benjamin Bedert, Nemanja Draganić, Alp Müyesser, Matías Pavez-Signé (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-08675.txt.

Introduction

Benjamin Bedert and colleagues prove that fairly dense Cayley graphs always hold a Hamilton cycle. Such a cycle exists in every large connected Cayley graph on n vertices whose degree clears n to some power below one. The result pushes the Lovász conjecture forward past the 2014 bar, and its proof swaps Szemerédi's regularity lemma for a leaner arithmetic version built for Cayley graphs.

Catalog record

CREATORBenjamin Bedert, Nemanja Draganić, Alp Müyesser, Matías Pavez-Signé
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58064
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.08675

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Lovász conjecture holds for moderately dense Cayley graphs Benjamin Bedert, Nemanja Draganić, Alp Müyesser, Matías Pavez-Signé Abstract We show that there is an absolute constant c > 0 c>0 such that every large connected n n -vertex Cayley graph with degree d ≥ n 1 − c d\geq 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 d\geq\varepsilon 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. 1 Introduction The Hamilton cycle problem is one of the most fundamental and widely studied questions in computer science and combinatorics. It was one of Karp’s original 21 NP-complete problems (see [ 18 ] ), and determining whether a general graph contains a Hamilton cycle remains a central challenge in the theory of algorithms and complexity. While the problem is computationally intractable in the worst case, a guiding philosophy in the field is that sufficient structure should render the problem solvable. In particular, it is a classical intuition that high symmetry might be enough to force the existence of a Hamilton cycle. This intuition is formalized in a celebrated conjecture of Lovász [ 24 ] from 1969, which asserts that every connected vertex-transitive graph has a Hamilton cycle. An even older version of this problem, posed by Rappaport-Strasser [ 29 ] in 1959, focuses on Cayley graphs. Given a group G and a subset S\subset G , the Cayley graph \mathrm{Cay}_{G}(S) is the graph whose vertices are the elements of G and all the edges are of the form \{g,gs\} with g\in G and s\in S . We will assume throughout the paper that G is finite and S is symmetric (i.e. s^{-1}\in S whenever s\in S ), in which case \mathrm{Cay}_{G}(S) is indeed a graph rather than a directed graph. Conjecture 1.1 . Every connected Cayley graph on a finite group with at least 3 elements is Hamiltonian. Despite over sixty years of research, Conjecture 1.1 remains wide open. It has been verified for abelian groups and specific families such as p -groups (for references and many more results see [ 22 ] ). Pak and Radoičić [ 28 ] showed that every finite group G of size at least 3 has a generating set S\subset G with |S|\leq\log_{2}|G| for which \mathrm{Cay}_{G}(S) is Hamiltonian. The conjecture is also known for “typical” generating sets: if S\subset G is a random subset of size |S|\geq C\log|G| (where C is a sufficiently large constant), then with high probability \mathrm{Cay}_{G}(S) is an expander graph (due to the Alon–Roichman theorem [ 1 ] ), and hence, is Hamiltonian, as established in a recent result [ 11 ] . For arbitrary Cayley graphs without typicality assumptions, Hamiltonicity is far from being established. In fact, there is no widespread consensus on whether the conjecture is true; indeed, Babai [ 3 ] conjectured that the statement is false, suggesting the existence of infinitely many connected Cayley graphs G where the longest cycle has length at most (1-c)|G| for a fixed constant c>0 . In the other direction, the longest cycle that is known to exist has length \Theta(n^{13/21}) [ 16 ] . On the other hand, for dense Cayley graphs, meaning those Cayley graphs with \Omega(n^{2}) edges, the Lovasz conjecture holds. This was established by Christofides, Hladkỳ and Máthé [ 8 ] who showed that for every \varepsilon>0 and n sufficiently large, every n -vertex connected Cayley graph 1 1 1 In fact, the result of [ 8 ] applies to the broader class of vertex-transitive graphs. of degree d\geq\varepsilon n has a Hamilton cycle. A key part of the argument in [ 8 ] is a structural result that decomposes a given vertex-transitive graph into components that satisfy a robust notion of connectivity. The proof in [ 8 ] uses Szemerédi’s regularity lemma to facilitate this decomposition. The regularity lemma is a powerful tool, however, it does not give useful information for sparse graphs, i.e. those with o(n^{2}) edges. The use of the regularity lemma also yields dependencies that are of tower-type, presenting a challenge for practical efficiency. Although the methods of Christofides, Hladkỳ and Máthé have influenced further results that also provide a structural decomposition of graphs into their expanding components while managing to avoid the use of the regularity lemma (see the work of Kühn, Lo, Osthus and Staden [ 19 ] and also [ 20 ] ), such results also come with costly exponential dependencies and do not apply to sparse graphs. In this paper, we break this density barrier encountered in previous approaches and confirm the Lovász conjecture for polynomially sparse Cayley graphs. Theorem 1.2 . There exists a constant c\geq 1/200 such that for all sufficiently large n , every connected n -vertex Cayley graph of degree d>n^{1-c} has a Hamilton cycle. A key feature of our approach is that it avoids the machinery of the regularity lemma, relying instead on mild forms of spectral expansion. One of the key ingredients in our proof is a weak arithmetic regularity lemma (see Theorem 2.2 below) recently introduced by Bedert, Bucić, Kravitz, Montgomery and Müyesser [ 4 , Theorem 1.5] in their work concerning Graham’s rearrangement conjecture. This weak arithmetic regularity lemma is a structural decomposition result, similar in spirit to the aforementioned work, but with much better quantitative dependencies. However, unlike those provided by the usual regularity lemma, the expansion conditions guaranteed by weak arithmetic regularity lemma are quite mild. Therefore, using this decomposition to produce a Hamilton cycle is a delicate task and is the crux of our work. To surmount this difficulty, we develop an efficient implementation of the absorption method specialised to sparse Cayley graphs. See Section 2 for a proof overview. 1.1 Future directions We made no effort to optimize the constant 1/200 that appears in Theorem 1.2 , however, our methods as presented here cannot be pushed beyond Cayley graphs of degree \sqrt{n} . Beyond this threshold, the weak arithmetic regularity lemma stops giving useful information and several of our arguments that build cycles out of small linear forests start to break down. Further progress requires a more efficient regularity lemma providing a decomposition into approximate subgroups rather than subgroups (see the discussion in [ 4 ] ) and also further ideas for finding Hamilton cycles in sparser graphs. Both of these aspects present considerable technical challenges, so we leave confirming the Lovász conjecture for graphs of degree n^{o(1)} for future work. It is likely that dense Cayley graphs might have enough structure to support Hamilton cycles, or even Hamilton decompositions, in a more robust sense than general Cayley graphs. For example, Alspach [ 2 ] conjectured that all abelian Cayley graphs of even degree admit a decomposition of their edge-set into Hamilton cycles. This is known to not hold for general (nonabelian) Cayley graphs [ 5 ] , but, under a density assumption as in the current paper, all even degree Cayley graphs may admit a Hamilton decomposition. In another direction, [ 31 ]

Read the complete text