A Cheeger inequality for the lower spectral gap

Abstract

Let $\Gamma$ be a Cayley graph, or a Cayley sum graph, or a twisted Cayley graph, or a twisted Cayley sum graph, or a vertex-transitive graph. Denote the degree of $\Gamma$ by $d$, its edge Cheeger constant by ${\mathfrak{h}}_{\Gamma }$, and its vertex Cheeger constant by $h_{\Gamma }$. Assume that $\Gamma$ is undirected, non-bipartite. We prove that the edge bipartiteness constant of $\Gamma$ is $\Omega ({\mathfrak{h}}_{\Gamma }/d)$, the vertex bipartiteness constant of $\Gamma$ is $\Omega (h_{\Gamma })$, and the smallest eigenvalue of the normalized adjacency operator of $\Gamma$ is $-1+\Omega (h_{\Gamma }^2/d^2)$. This answers in the affirmative a question of Moorman, Ralli and Tetali on the lower spectral gap of Cayley sum graphs.