Back to Search
Start Over
A Cheeger type inequality in finite Cayley sum graphs
- Publication Year :
- 2019
- Publisher :
- arXiv, 2019.
-
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)$.<br />Comment: Grant number added
- 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
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....4d4862bd7a5118278bad69a4090f6731
- Full Text :
- https://doi.org/10.48550/arxiv.1907.07710