A Cheeger type inequality in finite Cayley sum graphs

DOI10.5802/ALCO.166MaRDI QIDQ2039616zbMATH OpenOpenAlexFDO

Authors Arindam Biswas, Jyoti Prakash Saha

Publication date 5 July 2021

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1907.07710

zbMATH Keywords

Cheeger inequalityexpander graphsspectra of Cayley sum graphs

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

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+frach(G{)}^{4}eta,1-frach(G{)}^{2}2d^{2}ight]$, 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)$.

Recommendations

• On a Cheeger type inequality in Cayley graphs of finite groups
• Spectral bounds of directed Cayley graphs of finite groups
• Spectra of twists of Cayley and Cayley sum graphs
• On the spectral gap and the diameter of Cayley graphs
• On the spectrum of Cayley graphs

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A note on the isoperimetric constant
• Cayley sum graphs and eigenvalues of \((3,6)\)-fullerenes
• Connectivity of addition Cayley graphs
• Counting sets with small sumset and applications
• Counting sets with small sumset, and the clique number of random Cayley graphs
• Diameters and Eigenvalues
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Eigenvalues and expanders
• Expansion in finite simple groups of Lie type.
• Extractors in Paley graphs: a random model
• scientific article; zbMATH DE number 3501623 (Why is no real title available?)
• scientific article; zbMATH DE number 878889 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• On a Cheeger type inequality in Cayley graphs of finite groups
• On subgraphs of random Cayley sum graphs
• On the chromatic number of random Cayley graphs
• Subgroup perfect codes in Cayley sum graphs

Cited in

(10)

• On the bipartiteness constant and expansion of Cayley graphs
• Spectral bounds of directed Cayley graphs of finite groups
• On a Cheeger type inequality in Cayley graphs of finite groups
• Spectra of twists of Cayley and Cayley sum graphs
• The Cauchy-Schwarz inequality in Cayley graph and tournament structures on finite fields
• On the subgraphs of Cayley sum graphs
• A spectral bound for vertex-transitive graphs and their spanning subgraphs
• Vertex isoperimetry on signed graphs and spectra of non-bipartite Cayley and Cayley sum graphs
• On the cop number and the weak Meyniel conjecture for algebraic graphs
• On the nontrivial extremal eigenvalues of graphs

This page was built for publication: A Cheeger type inequality in finite Cayley sum graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2039616)