Functional limit theorems for random regular graphs

DOI10.1007/S00440-012-0447-YMaRDI QIDQ365705zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(29)

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

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)