The Lovász conjecture holds for moderately dense Cayley graphs

Abstract

We show that there is an absolute constant $c>0$ such that every large connected $n$-vertex Cayley graph with degree $d\ge 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\ge \epsilon 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.

16 pages, updated version features some corrections and simplifications