The rank of diluted random graphs

DOI10.1214/10-AOP567MaRDI QIDQ533748zbMATHFDO

Authors Charles Bordenave, Marc Lelarge, Justin Salez

Publication date 6 May 2011

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

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

zbMATH Keywords

adjacency matrixrandom matriceslocal weak convergencerandom graphsKarp and Sipser algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Spectrum, resolvent (47A10)

Abstract: We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs $(G_n{)}_{ngeq0}$ converging locally to a Galton--Watson tree $T$ (GWT), we provide an explicit formula for the asymptotic multiplicity of the eigenvalue 0 in terms of the degree generating function $ph{i}_{\ast }$ of $T$. In the first part, we show that the adjacency operator associated with $T$ is always self-adjoint; we analyze the associated spectral measure at the root and characterize the distribution of its atomic mass at 0. In the second part, we establish a sufficient condition on $ph{i}_{\ast }$ for the expectation of this atomic mass to be precisely the normalized limit of the dimension of the kernel of the adjacency matrices of $(G_n{)}_{ngeq0}$. Our proofs borrow ideas from analysis of algorithms, functional analysis, random matrix theory and statistical physics.

Recommendations

• The rank of diluted random graphs
• The rank of random graphs
• Spectra of large diluted but bushy random graphs
• The rank of random regular digraphs of constant degree
• Spectra of large random trees

Cites work

• scientific article; zbMATH DE number 5691097 (Why is no real title available?)
• scientific article; zbMATH DE number 3719745 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• Eigenvalue distribution of large weighted random graphs
• Extended states in the Anderson model on the Bethe lattice
• Karp-Sipser on random graphs with a fixed degree sequence
• Matchings on infinite graphs
• On the kernel of tree incidence matrices
• Processes on unimodular random networks
• Random symmetric matrices are almost surely nonsingular.
• Recurrence of distributional limits of finite planar graphs
• Resolvent of large random graphs
• Spectra of random linear combinations of matrices defined via representations and Coxeter generators of the symmetric group
• Stability of the absolutely continuous spectrum of random Schrödinger operators on tree graphs
• The rank of random graphs

Cited in

(32)

• Spectrum of non-Hermitian heavy tailed random matrices
• On quantum percolation in finite regular graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Existence of absolutely continuous spectrum for Galton-Watson random trees
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• Recent progress in combinatorial random matrix theory
• On the distribution of eigenvalues of increasing trees
• Singularity of the \(k\)-core of a random graph
• The rank of the sandpile group of random directed bipartite graphs
• Mean quantum percolation
• Atoms of the matching measure
• A new approach to the orientation of random hypergraphs
• Finding maximum matchings in random regular graphs in linear expected time
• Distribution of coefficients of rank polynomials for random sparse graphs
• Lifshitz tails on the Bethe lattice: A combinatorial approach
• The Minrank of Random Graphs
• Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
• Asymptotic representation theory and the spectrum of a random geometric graph on a compact Lie group
• Bernoulli random matrices
• Spectra of large diluted but bushy random graphs
• Sparse expanders have negative curvature
• The rank of random regular digraphs of constant degree
• On the rank, kernel, and core of sparse random graphs
• The rank of diluted random graphs
• Random simplicial complexes: around the phase transition
• Matchings on infinite graphs
• Matchings on trees and the adjacency matrix: A determinantal viewpoint
• Emergence of extended states at zero in the spectrum of sparse random graphs
• The rank of random graphs
• On the phase transition in random simplicial complexes
• On spectral portraits of incidence matrices of nearest neighbor graphs
• The rank of sparse random matrices

This page was built for publication: The rank of diluted random graphs

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