Odd cycles in symmetric Cayley graphs on prime cyclic groups

Abstract

Let $p$ be an odd prime and let $S\subseteq {\mathbb{Z}}_p$ be symmetric with $0\notin S$. Let $\Cay(\Z_p,S)$ be the undirected Cayley graph on ${\mathbb{Z}}_p$ in which $x$ and $y$ are adjacent if and only if $x-y\in S$. For $1\le \ell \le (p-1)/2$, define \[ \ex_{\Cay}(C_{2\ell+1},\Z_p)=\max\{|S|: S=-S,\ 0\notin S,\ \Cay(\Z_p,S)\text{ contains no }C_{2\ell+1}\}. \] Confirming a conjecture of Cashman and Kelley, we prove that if $p=2\ell +1$, then $\ex_{\Cay}(C_{2\ell+1},\Z_p)=0$, while if $p>2\ell +1$, then \[ \ex_{\Cay}(C_{2\ell+1},\Z_p)=2\floor{\frac{p+2\ell+1}{2(2\ell+1)}}. \] The proof combines a sharp additive zero-sum odd-girth argument with weak odd pancyclicity to transfer the result from odd-girth exclusion to fixed odd-cycle exclusion. We also give a canonical extremal family, an exact extremality criterion in terms of odd zero-sum avoidance, and an example showing that extremizers need not be dilates of the canonical construction.