Cycle lengths modulo $k$ in expanders

Abstract

Given a constant $\hat{I}\pm >0$, an $n$-vertex graph is called an $\hat{I}\pm$-expander if every set $X$ of at most $n/2$ vertices in $G$ has an external neighborhood of size at least $\hat{I}\pm |X|$. Addressing a question posed by Friedman and Krivelevich in [Combinatorica, 41(1), (2021), pp. 53--74], we prove the following result: Let $k>1$ be an integer with smallest prime divisor $p$. Then for $\hat{I}\pm >\frac{1}{p-1}$ every sufficiently large $\hat{I}\pm$-expanding graph contains cycles of length congruent to any given residue modulo $k$. This result is almost best possible, in the following sense: There exists an absolute constant $c>0$ such that for every integer $k$ with smallest prime divisor $p$ and for every positive $\hat{I}\pm <\frac{c}{p-1}$, there exist arbitrarily large $\hat{I}\pm$-expanding graphs with no cycles of length $r$ modulo $k$, for some $r\in \{0,\dots ,k-1\}$.

11 pages, no figures