The Maximum Number of Three Term Arithmetic Progressions, and Triangles in Cayley Graphs

Abstract

Let $G$ be a finite Abelian group. For a subset $S\subseteq G$, let $T_3(S)$ denote the number of length three arithemtic progressions in $S$ and Prob[$S$] $=\frac{1}{|S{|}^2}{\sum }_{x,y\in S}{1}_S(x+y)$. For any $q\ge 1$ and $\alpha \in [0,1]$, and any $S\subseteq G$ with $|S|=\frac{|G|}{q+\alpha }$, we show $\frac{T_3(S)}{|S{|}^2}$ and Prob[$S$] are bounded above by $\max \left(\frac{q^2-\alpha q+{\alpha }^2}{q^2},\frac{q^2+2\alpha q+4{\alpha }^2-6\alpha +3}{(q+1{)}^2},{\gamma }_0\right)$, where ${\gamma }_0<1$ is an absolute constant. As a consequence, we verify a graph theoretic conjecture of Gan, Loh, and Sudakov for Cayley graphs.

arXiv comment13 pages