The rank of random graphs |
| |
| Authors: | Kevin P Costello Van H Vu |
| |
| Institution: | 1. Institute for Advanced Study, Princeton, New Jersey 08540;2. Department of Mathematics, Rutgers, Piscataway, New Jersey 08854 |
| |
| Abstract: | We show that almost surely the rank of the adjacency matrix of the Erd?s‐Rényi random graph G(n,p) equals the number of nonisolated vertices for any c ln n/n ≤ p ≤ 1/2, where c is an arbitrary positive constant larger than 1/2. In particular, the adjacency matrix of the giant component (a.s.) has full rank in this range. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 |
| |
| Keywords: | random matrix random graph Littlewood‐Offord |
|
|
