The rank of random graphs

DOI10.1002/RSA.20219zbMATH Open1194.05083arXivmath/0606414OpenAlexW2950641406MaRDI QIDQ3608296FDOQ3608296

Kevin P. Costello, Van Vu

Publication date: 4 March 2009

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We show that almost surely the rank of the adjacency matrix of the Erd"os-R'enyi random graph $G(n,p)$ equals the number of non-isolated vertices for any $clnn/n<p<1/2$, where $c$ is an arbitrary positive constant larger than 1/2. In particular, the giant component (a.s.) has full rank in this range.

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

Recommendations

• The rank of random regular digraphs of constant degree
• The rank of diluted random graphs
• The rank of diluted random graphs
• On the rank of a random binary matrix
• The Evolution of Random Graphs

zbMATH Keywords

random matrixrandom graphLittlewood-Offord

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Random symmetric matrices are almost surely nonsingular.
• On the singularity probability of random Bernoulli matrices
• On the Probability That a Random ± 1-Matrix Is Singular
• On random ±1 matrices: Singularity and determinant
• On the Rank of Random Sparse Matrices

Cited In (27)

• Singularity of the \(k\)-core of a random graph
• Rank deficiency of random matrices
• Singularity of sparse random matrices: simple proofs
• On asymptotic properties of the rank of a special random adjacency matrix
• Hitting Time Theorems for Random Matrices
• Spectral gap in random bipartite biregular graphs and applications
• The rank of random regular digraphs of constant degree
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• Conformally covariant operators and conformal invariants on weighted graphs
• The rank of the sandpile group of random directed bipartite graphs
• Bilinear and quadratic variants on the Littlewood-Offord problem
• On the universality of the non-singularity of general Ginibre and Wigner random matrices
• Recent progress in combinatorial random matrix theory
• The smallest singular value of a shifted $d$-regular random square matrix
• The rank of diluted random graphs
• On the rank, kernel, and core of sparse random graphs
• On the Rank of Random Sparse Matrices
• Partitioning problems via random processes
• Invertibility of adjacency matrices for random \(d\)-regular graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• The Minrank of Random Graphs
• Geometric relationship between parallel hyperplanes, quadrics, and vertices of a hypercube
• Fixed energy universality of Dyson Brownian motion
• Distribution of coefficients of rank polynomials for random sparse graphs
• Sandpile groups of random bipartite graphs
• Expected values of parameters associated with the minimum rank of a graph
• The rank of sparse random matrices

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

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