Functional limit theorems for random regular graphs

DOI10.1007/S00440-012-0447-YzbMATH Open1271.05088arXiv1109.4094OpenAlexW2950184451MaRDI QIDQ365705FDOQ365705

Authors: Ioana Dumitriu, Tobias Johnson, Soumik Pal, Elliot Paquette 

Publication date: 9 September 2013

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: Consider d uniformly random permutation matrices on n labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random regular graph of degree 2d on n vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as n grows to infinity, either when d is kept fixed or grows slowly with n. In a suitable weak convergence framework, we prove that the (finite but growing in length) sequences of the number of short cycles and of cyclically non-backtracking walks converge to distributional limits. We estimate the total variation distance from the limit using Stein's method. As an application of these results we derive limits of linear functionals of the eigenvalues of the adjacency matrix. A key step in this latter derivation is an extension of the Kahn-Szemer'edi argument for estimating the second largest eigenvalue for all values of d and n.

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

Recommendations

• Cycles and eigenvalues of sequentially growing random regular graphs
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• Edge rigidity and universality of random regular graphs of intermediate degree
• Asymptotic normality of eigenvectors of a random regular graph [after Ágnes Backhausz and Balázs Szegedy]
• Central Limit Theorems and Asymptotic Spectral Analysis on Large Graphs

zbMATH Keywords

infinitely divisible distributionsPoisson approximationsparse random matricesrandom regular graphslinear eigenvalue statistics

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Functional limit theorems; invariance principles (60F17)

Cites Work

• On tail probabilities for martingales
• The eigenvalues of random symmetric matrices
• Fluctuations of eigenvalues and second order Poincaré inequalities
• An introduction to random matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation theory and approximation practice
• The central limit theorem for local linear statistics in classical compact groups and related combinatorial identities
• Random graphs.
• Title not available (Why is that?)
• Ramanujan graphs
• CLT for linear spectral statistics of large-dimensional sample covariance matrices.
• Characteristic vectors of bordered matrices with infinite dimensions
• Title not available (Why is that?)
• Some Probabilistic Aspects of Set Partitions
• Short cycles in random regular graphs
• On fluctuations of eigenvalues of random Hermitian matrices.
• A proof of Alon’s second eigenvalue conjecture and related problems
• Central limit theorem for linear eigenvalue statistics of random matrices with independent entries
• The expected eigenvalue distribution of a large regular graph
• Some limit theorems for the eigenvalues of a sample covariance matrix
• Central limit theorem for traces of large random symmetric matrices with independent matrix elements
• Sparse random graphs: eigenvalues and eigenvectors
• Fluctations of the empirical law of large random matrices
• Sparse regular random graphs: spectral density and eigenvectors
• The cycle structure of random permutations
• Linear functionals of eigenvalues of random matrices
• Title not available (Why is that?)
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Orthogonal polynomials and fluctuations of random matrices
• Wigner matrices
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• Eigenvalue distributions of random permutation matrices.
• Word maps and spectra of random graph lifts
• Permutation Pseudographs and Contiguity
• Random matrices, nonbacktracking walks, and orthogonal polynomials
• Subgraphs of random \(k\)-edge-coloured \(k\)-regular graphs
• Title not available (Why is that?)
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Spectral techniques applied to sparse random graphs
• Spectra of lifted Ramanujan graphs
• Title not available (Why is that?)
• Exchangeable pairs and Poisson approximation

Cited In (28)

• Title not available (Why is that?)
• Structure of eigenvectors of random regular digraphs
• Cycles and eigenvalues of sequentially growing random regular graphs
• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• A random walk approach to linear statistics in random tournament ensembles
• The spectral gap of dense random regular graphs
• Spectrum of random d‐regular graphs up to the edge
• Local Kesten-McKay law for random regular graphs
• Freely Independent Coin Tosses, Standard Young Tableaux, and the Kesten–McKay Law
• Exchangeable pairs, switchings, and random regular graphs
• Expansion of random graphs: new proofs, new results
• Discrepancy properties for random regular digraphs
• The random transposition dynamics on random regular graphs and the Gaussian free field
• On fluctuations of eigenvalues of random permutation matrices
• Statistics of finite degree covers of torus knot complements
• Reliable Spanners for Metric Spaces
• Sparse random tensors: concentration, regularization and applications
• Edge rigidity and universality of random regular graphs of intermediate degree
• Global eigenvalue fluctuations of random biregular bipartite graphs
• On the second eigenvalue of random bipartite biregular graphs
• Universality and sharp matrix concentration inequalities
• Sparse matrices: convergence of the characteristic polynomial seen from infinity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Central limit theorems for linear statistics of heavy tailed random matrices
• The limit theorem with respect to the matrices on non-backtracking paths of a graph
• Size biased couplings and the spectral gap for random regular graphs
• On the almost eigenvectors of random regular graphs

This page was built for publication: Functional limit theorems for random regular graphs

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