A proof of Alon’s second eigenvalue conjecture and related problems
From MaRDI portal
Publication:3521433
DOI10.1090/memo/0910zbMath1177.05070arXivcs/0405020OpenAlexW1650240946MaRDI QIDQ3521433
Publication date: 22 August 2008
Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0405020
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items
Assouad-Nagata dimension and gap for ordered metric spaces ⋮ Mean-Field Approximations for Stochastic Population Processes with Heterogeneous Interactions ⋮ A randomized construction of high girth regular graphs ⋮ A note on the trace method for random regular graphs ⋮ The spectral gap of random regular graphs ⋮ Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree ⋮ Global eigenvalue fluctuations of random biregular bipartite graphs ⋮ Near optimal spectral gaps for hyperbolic surfaces ⋮ On the minimum bisection of random 3-regular graphs ⋮ The limit theorem with respect to the matrices on non-backtracking paths of a graph ⋮ Combinatorial statistics and the sciences ⋮ Random matrices and random graphs ⋮ Spectrum of random d‐regular graphs up to the edge ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Towards optimal spectral gaps in large genus ⋮ On the second eigenvalue of random bipartite biregular graphs ⋮ Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs ⋮ A Ramsey–Turán theory for tilings in graphs ⋮ Statistics of finite degree covers of torus knot complements ⋮ Simple versus nonsimple loops on random regular graphs ⋮ The rank of sparse random matrices ⋮ Spectral gap in random bipartite biregular graphs and applications ⋮ Explicit spectral gaps for random covers of Riemann surfaces ⋮ An entropic proof of cutoff on Ramanujan graphs ⋮ Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices ⋮ Quantum ergodicity for quantum graphs without back-scattering ⋮ Wright-Fisher diffusions in stochastic spatial evolutionary games with death-birth updating ⋮ Adjacency matrices of random digraphs: singularity and anti-concentration ⋮ Graphs, Vectors, and Matrices ⋮ Benjamini-Schramm convergence and spectra of random hyperbolic surfaces of high genus ⋮ Cutoff on all Ramanujan graphs ⋮ Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes ⋮ Finding structure in sequences of real numbers via graph theory: a problem list ⋮ Isoperimetric inequalities in simplicial complexes ⋮ Voter and majority dynamics with biased and stubborn agents ⋮ Functional limit theorems for random regular graphs ⋮ \(k\)-planar crossing number of random graphs and random regular graphs ⋮ Explicit expanding expanders ⋮ A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\) ⋮ The geometry of spontaneous spiking in neuronal networks ⋮ Ramanujan coverings of graphs ⋮ Spectra of edge-independent random graphs ⋮ The spectra of random mixed graphs ⋮ Graphs with high second eigenvalue multiplicity ⋮ Simple random walk on long range percolation clusters. I: Heat kernel bounds ⋮ On the almost eigenvectors of random regular graphs ⋮ Local Kesten-McKay law for random regular graphs ⋮ Sparse matrices: convergence of the characteristic polynomial seen from infinity ⋮ The replicator equation in stochastic spatial evolutionary games ⋮ Shaping bursting by electrical coupling and noise ⋮ Sofic entropy of Gaussian actions ⋮ Correlation Bounds for Distant Parts of Factor of IID Processes ⋮ Giant vacant component left by a random walk in a random \(d\)-regular graph ⋮ The Kadison-Singer problem for the direct sum of matrix algebras ⋮ Fighting constrained fires in graphs ⋮ Edge rigidity and universality of random regular graphs of intermediate degree ⋮ A model for random three-manifolds ⋮ Mixing in High-Dimensional Expanders ⋮ The Zero Forcing Number of Graphs ⋮ Aldous’s spectral gap conjecture for normal sets ⋮ Structure of eigenvectors of random regular digraphs ⋮ On the spectra of general random mixed graphs ⋮ On constructing expander families of G-graphs ⋮ Formal Zeta function expansions and the frequency of Ramanujan graphs ⋮ The spectral gap of dense random regular graphs ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Random Latin squares and 2-dimensional expanders ⋮ Reconstruction and estimation in the planted partition model ⋮ Expansion of random graphs: new proofs, new results ⋮ Explicit expanders of every degree and size ⋮ Comparison of Metric Spectral Gaps ⋮ Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs ⋮ Size biased couplings and the spectral gap for random regular graphs ⋮ Component structure of the vacant set induced by a random walk on a random graph ⋮ On graphs whose spectral radius is bounded by \(\frac{3}{2}\sqrt{2}\) ⋮ Sparse regular random graphs: spectral density and eigenvectors ⋮ Exchangeable pairs, switchings, and random regular graphs ⋮ Edge intersection graphs of systems of paths on a grid with a bounded number of bends ⋮ Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk ⋮ Unnamed Item ⋮ Spectra of lifted Ramanujan graphs ⋮ Bounding the gap between extremal Laplacian eigenvalues of graphs ⋮ Cutoff phenomena for random walks on random regular graphs ⋮ Word maps and spectra of random graph lifts ⋮ The random transposition dynamics on random regular graphs and the Gaussian free field ⋮ Gonality of expander graphs ⋮ A generalized Alon-Boppana bound and weak Ramanujan graphs ⋮ Statistical properties of zeta functions' zeros ⋮ Stein's method for stationary distributions of Markov chains and application to Ising models ⋮ Recent progress in combinatorial random matrix theory ⋮ Vertex percolation on expander graphs ⋮ Recent results of quantum ergodicity on graphs and further investigation ⋮ Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey ⋮ Clustering coefficients of large networks ⋮ Limiting eigenvalue distribution of random matrices of Ihara zeta function of long-range percolation graphs ⋮ Graphs with Many Strong Orientations ⋮ Viral Processes by Random Walks on Random Regular Graphs ⋮ Convex structures revisited ⋮ Precise asymptotics of some meeting times arising from the voter model on large random regular graphs ⋮ On the Expansion of Group-Based Lifts ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Estimating graph parameters with random walks ⋮ Babai's conjecture for high-rank classical groups with random generators ⋮ Expander graphs in pure and applied mathematics ⋮ Measure preserving words are primitive ⋮ Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an Appendix by Warren Dicks ⋮ Mixing time and eigenvalues of the abelian sandpile Markov chain ⋮ Periodic Walks on Large Regular Graphs and Random Matrix Theory ⋮ Typicality and entropy of processes on infinite trees ⋮ The non-backtracking spectrum of the universal cover of a graph ⋮ Rumor spreading on random regular graphs and expanders ⋮ Random Steiner systems and bounded degree coboundary expanders of every dimension ⋮ Eigenvalues of random lifts and polynomials of random permutation matrices ⋮ The Size Ramsey Number of Graphs with Bounded Treewidth ⋮ Explicit Near-Ramanujan Graphs of Every Degree ⋮ On the Expansion of Group-Based Lifts ⋮ Quantum ergodicity on large regular graphs ⋮ Interlacing families. I: Bipartite Ramanujan graphs of all degrees ⋮ New and explicit constructions of unbalanced Ramanujan bipartite graphs ⋮ Synchronization of coupled chaotic maps
