A nearly linear bound for the Lovász conjecture
Abstract
The celebrated conjecture of Lovász from 1969 asks whether every connected vertex-transitive graph has a Hamiltonian path. Bucić, Christoph, Pokrovskiy and Steiner recently proved that every such graph on n vertices contains a cycle of length n2/3−o(1). In this paper, we improve this bound to n1−o(1). Our proof uses a structure theorem of Tessera and Tointon to first obtain a partition of the vertex set into sets of small diameter in the original graph. When the parts are large, we repeatedly traverse a spanning tree of maximum degree at most three in the quotient graph, and use the Lovász local lemma to join random short paths along this traversal and extract a long path in the original graph. When the parts are small, we apply Babai's contraction lemma to reduce the problem to finding a long path in a connected Cayley graph of a nilpotent group with boundedly many generators and bounded nilpotency class, and then show that such a Cayley graph on m vertices contains a path on m1−o(1) vertices.
Related
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- A near-linear upper bound for Burr's conjecture
- A linear bound for Fujita's freeness conjecture
- Presenting a proof of the Kannan-Lovasz-Simonovits conjecture
- Stability and exact extremal colourings for the Alon--Frankl--Lovász bound
BibTeX
@misc{li2026nearly,
title = {{A nearly linear bound for the Lovász conjecture}},
author = {Bowen Li and Abhishek Methuku},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.38135},
eprint = {2609.38135},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38135},
}
RIS
TY - UNPB
TI - A nearly linear bound for the Lovász conjecture
AU - Bowen Li
AU - Abhishek Methuku
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2609.38135
UR - https://arxiv.org/abs/2609.38135
AB - The celebrated conjecture of Lovász from 1969 asks whether every connected vertex-transitive graph has a Hamiltonian path. Bucić, Christoph, Pokrovskiy and Steiner recently proved that every such graph on n vertices contains a cycle of length n^2/3−o(1). In this paper, we improve this bound to n^1−o(1). Our proof uses a structure theorem of Tessera and Tointon to first obtain a partition of the vertex set into sets of small diameter in the original graph. When the parts are large, we repeatedly traverse a spanning tree of maximum degree at most three in the quotient graph, and use the Lovász local lemma to join random short paths along this traversal and extract a long path in the original graph. When the parts are small, we apply Babai's contraction lemma to reduce the problem to finding a long path in a connected Cayley graph of a nilpotent group with boundedly many generators and bounded nilpotency class, and then show that such a Cayley graph on m vertices contains a path on m^1−o(1) vertices.
ER -