The spectral gap of sparse random digraphs

DOI10.1214/20-AIHP1090zbMath1468.05093arXiv1708.00530OpenAlexW3160500254MaRDI QIDQ2041813

Simon Coste

Publication date: 23 July 2021

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

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

zbMATH Keywords

random graphsdegree sequencesecond eigenvaluehigh trace methoddirected configuration graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random matrices (algebraic aspects) (15B52) Directed graphs (digraphs), tournaments (05C20) Local spectral properties of linear operators (47A11) Density (toughness, etc.) (05C42)

Related Items

Spectral gap in random bipartite biregular graphs and applications ⋮ Detection thresholds in very sparse matrix completion ⋮ Random matrices and random graphs ⋮ Sparse matrices: convergence of the characteristic polynomial seen from infinity ⋮ On the second eigenvalue of random bipartite biregular graphs ⋮ Spectra of random regular hypergraphs ⋮ On arbitrary compression for decentralized consensus and stochastic optimization over directed networks ⋮ Eigenvalues of the non-backtracking operator detached from the bulk

Cites Work

• Unnamed Item
• Unnamed Item
• Cutoff on all Ramanujan graphs
• Around the circular law
• Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
• Norms and exclusion theorems
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• Cutoff phenomena for random walks on random regular graphs
• Eigenvalues and expanders
• The eigenvalues of random symmetric matrices
• On the second eigenvalue of a graph
• On the spectrum of the sum of generators for a finitely generated group
• The spectral gap of dense random regular graphs
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Size biased couplings and the spectral gap for random regular graphs
• Circular law for the sum of random permutation matrices
• Random walk on sparse random digraphs
• Circular law theorem for random Markov matrices
• Circular law for sparse random regular digraphs
• Spectrum of large random reversible Markov chains: two examples
• Symmetric Random Walks on Groups
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Expander graphs and their applications
• A proof of alon's second eigenvalue conjecture
• Mathematical Aspects of Mixing Times in Markov Chains
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The cutoff phenomenon in finite Markov chains.
• Community detection thresholds and the weak Ramanujan property
• The circular law for random regular digraphs with random edge weights
• Spectrum of large random Markov chains: Heavy-tailed weights on the oriented complete graph