On the Bipartiteness Constant and Expansion of Cayley Graphs

Nina Moorman, Peter Ralli, Prasad Tetali

Let $G$ be a finite, undirected $d$-regular graph and $A(G)$ its normalized adjacency matrix, with eigenvalues $1={\lambda }_1(A)\ge \cdots \ge {\lambda }_n\ge -1$. It is a classical fact that $λ…