1. A Cheeger type inequality in finite Cayley sum graphs
- Author
-
Arindam Biswas and Jyoti Prakash Saha
- Subjects
Vertex (graph theory) ,Finite group ,Cayley graph ,010102 general mathematics ,Spectrum (functional analysis) ,05C25, 05C50, 05C75 ,0102 computer and information sciences ,Group Theory (math.GR) ,01 natural sciences ,Cheeger constant (graph theory) ,Combinatorics ,010201 computation theory & mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Interval (graph theory) ,Adjacency list ,Expander graph ,Combinatorics (math.CO) ,0101 mathematics ,Mathematics - Group Theory ,Mathematics - 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)$., Comment: Grant number added
- Published
- 2019
- Full Text
- View/download PDF