On the Bipartiteness Constant and Expansion of Cayley Graphs

Let $G$ be a finite, undirected $d$-regular graph and $A(G)$ its normalized adjacency matrix, with eigenvalues $1 = \lambda_1(A)\geq \dots \ge \lambda_n \ge -1$\mathrm{.}Itisaclassicalfactthat$\lambda_n = -1$ifandonlyif$G$ is bipartite. Our main result provides a quantitative separation of ${\lambda }_n$ from $-1$ in the case of Cayley graphs, in terms of their expansion. Denoting $h_{out}$ by the (outer boundary) vertex expansion of $G$, we show that if $G$ is a non-bipartite Cayley graph (constructed using a group and a symmetric generating set of size $d$) then ${\lambda }_n\ge -1+c{h}_{out}^2\mathrm{/}{d}^2,$ for $c$ an absolute constant. We exhibit graphs for which this result is tight up to a factor depending on $d$. This improves upon a recent result by Biswas and Saha who showed ${\lambda }_n\ge -1+h_{out}^4\mathrm{/}(2^9{d}^8)\mathrm{.}$ We also note that such a result could not be true for general non-bipartite graphs.