On the second eigenvalue of a graph
From MaRDI portal
Let \(G\) be a regular graph of valency \(d\) containing two edges at distance \(2k+2\). The author shows that the second largest eigenvalue of the adjacency matrix of \(G\) is at least \[ 2\sqrt{d-1}-{2\sqrt{d-1}-1\over k+1}. \] This implies an earlier bound of Alon and Boppana (stated without proof in: \textit{N. Alon} [Eigenvalues and expanders, Combinatorica 6, No. 2, 83-96 (1986; Zbl 0661.05053)]). The proof is short and direct.
Recommendations
- Tight estimates for eigenvalues of regular graphs
- A proof of alon's second eigenvalue conjecture
- On the order of regular graphs with fixed second largest eigenvalue
- Maximizing the order of a regular graph of given valency and second eigenvalue
- Regular graphs whose second largest eigenvalue is at most 1
Cites work
Cited in
(only showing first 100 items - show all)- Some geometric aspects of graphs and their eigenfunctions
- Laplacian matrices of graphs: A survey
- Relative expanders or weakly relatively Ramanujan graphs.
- Ramanujan coverings of graphs
- Equiangular lines and spherical codes in Euclidean space
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Size biased couplings and the spectral gap for random regular graphs
- A new upper bound on the Cheeger number of a graph
- On second order degree of graphs
- The Colin de Verdière parameter, excluded minors, and the spectral radius
- The spectral gap of sparse random digraphs
- LDPC codes constructed from cubic symmetric graphs
- Ramsey numbers involving an odd cycle and large complete graphs in three colors
- Measurable equidecompositions for group actions with an expansion property
- High-girth near-Ramanujan graphs with localized eigenvectors
- Finding structure in sequences of real numbers via graph theory: a problem list
- Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines
- Line-graph lattices: Euclidean and non-Euclidean flat bands, and implementations in circuit quantum electrodynamics
- Ramsey numbers and bipartite Ramsey numbers via quasi-random graphs
- On the order of regular graphs with fixed second largest eigenvalue
- A connection between a question of Bermond and Bollobás and Ramanujan graphs
- Explicit expanders of every degree and size
- \(L^p\)-expander graphs
- Approximate Moore graphs are good expanders
- Stein's method for stationary distributions of Markov chains and application to Ising models
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Shift lifts preserving Ramanujan property
- Three conjectures in extremal spectral graph theory
- Isoperimetric inequalities in simplicial complexes
- On spectral radii of unraveled balls
- Commute times for a directed graph using an asymmetric Laplacian
- Kesten's theorem for invariant random subgroups.
- On the sizes of expander graphs and minimum distances of graph codes
- On the extreme eigenvalues of regular graphs.
- A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\)
- On weighted spectral radius of unraveled balls and normalized Laplacian eigenvalues
- Sparse matrices: convergence of the characteristic polynomial seen from infinity
- Aldous' spectral gap property for normal Cayley graphs on symmetric groups
- Maximizing the order of a regular graph of given valency and second eigenvalue
- Rumor spreading on random regular graphs and expanders
- Cryptographic hash functions from sequences of lifted Paley graphs
- Simplicial complexes: spectrum, homology and random walks
- Modular orientations of random and quasi-random regular graphs
- A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem
- Word maps and spectra of random graph lifts
- Graph-theoretic design and analysis of key predistribution schemes
- On the second Laplacian spectral moment of a graph
- Local resilience and hamiltonicity maker-breaker games in random regular graphs
- Graphs, vectors, and matrices
- Cutoff on all Ramanujan graphs
- NON-BACKTRACKING RANDOM WALKS MIX FASTER
- A combinatorial trace method: counting closed walks to assay graph eigenvalues
- Expander graphs and their applications
- A proof of Alon’s second eigenvalue conjecture and related problems
- Diameters and Eigenvalues
- scientific article; zbMATH DE number 475377 (Why is no real title available?)
- Random Cayley graphs and expanders
- Interlacing families. IV: Bipartite Ramanujan graphs of all sizes
- Sign rank versus Vapnik-Chervonenkis dimension
- On the first and second eigenvalue of finite and infinite uniform hypergraphs
- Explicit bounds from the Alon-Boppana theorem
- Ramanujan complexes and high dimensional expanders
- scientific article; zbMATH DE number 871421 (Why is no real title available?)
- scientific article; zbMATH DE number 6117015 (Why is no real title available?)
- Expansion of random graphs: new proofs, new results
- Generalized group-subgroup pair graphs
- Triangle‐factors in pseudorandom graphs
- On the expansion of group-based lifts
- Graph powering and spectral robustness
- Organisational hierarchy constructions with easy Kuramoto synchronisation
- A relationship between the second largest eigenvalue and local valency of an edge-regular graph
- Proportional volume sampling and approximation algorithms for \(A\)-optimal design
- A combinatorial proof of Ihara-Bass's formula for the zeta function of regular graphs
- Open problems in the spectral theory of signed graphs
- On the expansion of group-based lifts
- Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that
- Spectra of lifted Ramanujan graphs
- Explicit Near-Ramanujan Graphs of Every Degree
- Second largest eigenpair statistics for sparse graphs
- New spectral lower bounds on the bisection width of graphs
- Cycle density in infinite Ramanujan graphs
- Graphs with high second eigenvalue multiplicity
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- A note on the trace method for random regular graphs
- Gap sets for the spectra of cubic graphs
- The spectral gap of random regular graphs
- Petals and books: The largest Laplacian spectral gap from 1
- Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)
- Graph rigidity properties of Ramanujan graphs
- On the eigenvalues of the graphs D(5,q)
- Paradigms for Unconditional Pseudorandom Generators
- On the first two eigenvalues of regular graphs
- On the second eigenvalue of random bipartite biregular graphs
- A note on pseudorandom Ramsey graphs
- Alon-Boppana-type bounds for weighted graphs
- Local and global expansion in random geometric graphs
- Block codes for dyadic phase shift keying
- Strong blocking sets and minimal codes from expander graphs
- Proactive secret sharing with constant communication
- On minimizing the energy of a spherical graph representation
This page was built for publication: On the second eigenvalue of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1182585)
