The rank of random graphs

DOI10.1002/RSA.20219MaRDI QIDQ3608296zbMATHOpenAlexFDO

Authors Kevin P. Costello, Van Vu

Publication date 4 March 2009

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

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

zbMATH Keywords

random matrixrandom graphLittlewood-Offord

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(31)

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