A Cheeger type inequality in finite Cayley sum graphs

Abstract

Let $G$ be a finite group and $S$ be a symmetric generating set of $G$ with $|S|=d$. We show that if the undirected Cayley sum graph $C_{\Sigma }(G,S)$ is an expander graph and is non-bipartite, then the spectrum of its normalised adjacency operator is bounded away from $-1$. We also establish an explicit lower bound for the spectrum of these graphs, namely, the non-trivial eigenvalues of the normalised adjacency operator lies in the interval $\left(-1+\frac{h(G{)}^4}{\eta },1-\frac{h(G{)}^2}{2d^2}\right]$, where $h(G)$ denotes the (vertex) Cheeger constant of the $d$-regular graph $C_{\Sigma }(G,S)$ and $\eta =2^9{d}^8$. Further, we improve upon a recently obtained bound on the non-trivial spectrum of the normalised adjacency operator of the non-bipartite Cayley graph $C(G,S)$.

arXiv commentGrant number added