Long Directed Cycles in Vertex-Transitive Digraphs

Abstract

The search for Hamiltonian cycles in vertex-transitive graphs and digraphs is a classical problem at the interface of graph theory and group theory. In the undirected setting, this goes back to the well-known conjectures of Lovász and Thomassen concerning Hamiltonian paths and cycles in connected vertex-transitive graphs. Dating back to Rankin's 1946 work, the directed analogue has an even longer history, linking the search for long cycles to classical group-rearrangement problems. Trotter and Erdős showed in 1978 that connected vertex-transitive digraphs need not be Hamiltonian. In light of this result, Alspach asked in 1981 whether there exist connected vertex-transitive digraphs whose longest directed cycle misses arbitrarily many vertices. This question was only recently resolved by Bucić, Hendrey, Mohar, Steiner and Yepremyan, who constructed connected vertex-transitive digraphs on $n$ vertices whose longest directed cycle omits $(1-o(1))\log n$ vertices. They conjectured that the number of omitted vertices can grow linearly with $n$, remarking that it would already be interesting to improve their logarithmic lower bound to a polynomial bound. In this paper, we confirm their conjecture in a strong form by constructing infinitely many connected vertex-transitive digraphs on $n$ vertices whose longest directed cycle omits at least $n/12$ vertices. In the same work, Bucić, Hendrey, Mohar, Steiner and Yepremyan also proved that every connected vertex-transitive digraph on $n$ vertices contains a directed cycle of length $\Omega (n^{1/3})$, giving the first lower bound for this problem that grows with $n$. We improve this to $\Omega (\sqrt{n})$, matching the order of Babai's classical theorem from 1979 for undirected vertex-transitive graphs.

14 pages