arXiv:math/0606414 Abstract

arXiv:math/0606414 [math.PR]Abstract References Reviews Resources

The Rank of Random Graphs

Published 2006-06-17Version 1

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 $c\ln n/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.

Comments: 19 pages, no figures

Categories: math.PR, math.CO

Subjects: 15A52

Keywords: random graph, arbitrary positive constant larger, full rank, adjacency matrix, giant component

Related articles: Most relevant | Search more

arXiv:math/0610459 [math.PR] (Published 2006-10-15, updated 2016-07-31)

The mixing time of the giant component of a random graph

Itai Benjamini, Gady Kozma, Nicholas Wormald

arXiv:1811.07554 [math.PR] (Published 2018-11-19, updated 2020-11-28)

Upper Tails for Edge Eigenvalues of Random Graphs

Bhaswar B. Bhattacharya, Shirshendu Ganguly

arXiv:1504.01999 [math.PR] (Published 2015-04-08)