On the spectral gap and the diameter of Cayley graphs (Q2234376): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3207781564 / rank | |||
Normal rank |
Latest revision as of 10:40, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the spectral gap and the diameter of Cayley graphs |
scientific article |
Statements
On the spectral gap and the diameter of Cayley graphs (English)
0 references
19 October 2021
0 references
In this paper, the author gives an improved bound for the spectral gap for a Cayley graph, that is, the difference between the valency and the second largest eigenvalue \(\lambda_1\) (of the adjacency matrix). Let \(G\) be a group and \(S\) a subset of \(G\) not containing the identity and closed under taking inverses. We are only interested in the case when \(S\) generates \(G\). In this case, the Cayley graph \(\mathrm{Cay}(S)\) is connected, say with diameter \(d\). The previous known bound was \(\lambda_1\mathrm{Cay}(S)\geq \frac{1}{2d^2|S|}\). In this paper, it is shown that \(\lambda_1\mathrm{Cay}(S)\geq \frac{|G|}{d|S|^d}\). The author shows that in many cases the new bound is better than the old bound.
0 references
spectral gap
0 references
expander graphs
0 references
0 references