The rank of diluted random graphs

DOI10.1214/10-AOP567zbMATH Open1298.05283arXiv0907.4244MaRDI QIDQ533748FDOQ533748

Marc Lelarge, Justin Salez, Charles Bordenave

Publication date: 6 May 2011

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

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}_{*}$ 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}_{*}$ 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.

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

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

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)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Title not available (Why is that?)
• Processes on unimodular random networks
• Matchings on infinite graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random symmetric matrices are almost surely nonsingular.
• Stability of the absolutely continuous spectrum of random Schrödinger operators on tree graphs
• Eigenvalue distribution of large weighted random graphs
• Title not available (Why is that?)
• Resolvent of large random graphs
• Extended states in the Anderson model on the Bethe lattice
• Karp–Sipser on Random Graphs with a Fixed Degree Sequence
• The rank of random graphs
• Spectra of random linear combinations of matrices defined via representations and Coxeter generators of the symmetric group
• On the kernel of tree incidence matrices

Cited In (30)

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