Longer cycles in vertex transitive graphs

Abstract

In 1979 Babai found a clever argument to prove that every connected vertex transitive graph on $n\ge 3$ vertices contains a cycle of length at least $\sqrt{3n}$. Here we modify his approach to show that such graphs must contain a cycle of length at least $(1-o(1))n^{3/5}$.

4 pages