Size biased couplings and the spectral gap for random regular graphs

DOI10.1214/17-AOP1180zbMath1386.05105arXiv1510.06013OpenAlexW1798337851MaRDI QIDQ1747748

Xianqiang Yang

Publication date: 27 April 2018

Published in: The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

Stein's methodsecond eigenvalueconcentrationrandom regular graphsize biased couplingAlon's conjecture

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random matrices (algebraic aspects) (15B52)

Related Items (27)

Relaxation of monotone coupling conditions: Poisson approximation and beyond ⋮ A central limit theorem for descents of a Mallows permutation and its inverse ⋮ Concentration inequalities from monotone couplings for graphs, walks, trees and branching processes ⋮ Mean-Field Approximations for Stochastic Population Processes with Heterogeneous Interactions ⋮ The spectral gap of random regular graphs ⋮ Global eigenvalue fluctuations of random biregular bipartite graphs ⋮ Local Kesten-McKay law for random regular graphs ⋮ Concentration inequalities using approximate zero bias couplings with applications to Hoeffding’s statistic under the Ewens distribution ⋮ On the second eigenvalue of random bipartite biregular graphs ⋮ Card guessing and the birthday problem for sampling without replacement ⋮ Particle density in diffusion-limited annihilating systems ⋮ A discrete log-Sobolev inequality under a Bakry-Émery type condition ⋮ Central moment inequalities using Stein's method ⋮ Edge rigidity and universality of random regular graphs of intermediate degree ⋮ Structure of eigenvectors of random regular digraphs ⋮ The spectral gap of dense random regular graphs ⋮ Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models ⋮ Size bias for one and all ⋮ Reliable communication over highly connected noisy networks ⋮ Infection spread for the frog model on trees ⋮ The spectral gap of sparse random digraphs ⋮ Sparse random tensors: concentration, regularization and applications ⋮ Graphs with Many Strong Orientations ⋮ Sherali-adams strikes back ⋮ Dirac’s theorem for random regular graphs ⋮ Weighted Poincaré inequalities, concentration inequalities and tail bounds related to Stein kernels in dimension one ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Functional limit theorems for random regular graphs
• Fundamentals of Stein's method
• Bounded size bias coupling: a gamma function bound, and universal Dickman-function behavior
• On the singularity of adjacency matrices for random regular digraphs
• Spectra of lifted Ramanujan graphs
• Applications of Stein's method for concentration inequalities
• Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings
• Bulk eigenvalue statistics for random regular graphs
• Sparse regular random graphs: spectral density and eigenvectors
• Concentration of measures via size-biased couplings
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Eigenvalues and expanders
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• On the second eigenvalue of a graph
• Level-spacing distributions and the Airy kernel
• The spectral gap of dense random regular graphs
• Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models
• Size bias for one and all
• Short cycles in random regular graphs
• On the second eigenvalue of hypergraphs
• Exchangeable pairs, switchings, and random regular graphs
• Stein's method for concentration inequalities
• The spectral gap of random graphs with given expected degrees
• Concentration inequalities via zero bias couplings
• Random regular graphs of high degree
• Discrepancy properties for random regular digraphs
• Expander graphs in pure and applied mathematics
• Permutation Pseudographs and Contiguity
• 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 and related problems
• The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs
• The Probability That a Random Multigraph is Simple
• Normal Approximation by Stein’s Method
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Multivariate normal approximations by Stein's method and size bias couplings
• Sparse random graphs: Eigenvalues and eigenvectors
• Matrix Completion From a Few Entries
• Spectral techniques applied to sparse random graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Local Semicircle Law for Random Regular Graphs
• CLT-related large deviation bounds based on Stein's method
• Spectra of random graphs with given expected degrees
• On the probability of large deviations from the expectation for sums of bounded, independent random variables
• A Combinatorial Central Limit Theorem

This page was built for publication: Size biased couplings and the spectral gap for random regular graphs