OpenAlex ·
A nearly linear bound for the Lovász conjecture
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.38135
- Original
- Read it at the publisher
- Topics
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 $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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
The Reach of Abelian Covers in Hypergraphs
MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One
Order-Optimal Systematic Permutation Codes for Correcting t Deletions
Quantum State Routing and Perfect State Transfer on Signed Graphs under Environmental Noise
On the nonnegativity of monomial immanants for hook partitions
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.