Back to Search
Start Over
Adjacency matrices of random digraphs: Singularity and anti-concentration.
- Source :
-
Journal of Mathematical Analysis & Applications . Jan2017, Vol. 445 Issue 2, p1447-1491. 45p. - Publication Year :
- 2017
-
Abstract
- Let D n , d be the set of all d -regular directed graphs on n vertices. Let G be a graph chosen uniformly at random from D n , d and M be its adjacency matrix. We show that M is invertible with probability at least 1 − C ln 3 d / d for C ≤ d ≤ c n / ln 2 n , where c , C are positive absolute constants. To this end, we establish a few properties of d -regular directed graphs. One of them, a Littlewood–Offord type anti-concentration property, is of independent interest. Let J be a subset of vertices of G with | J | ≈ n / d . Let δ i be the indicator of the event that the vertex i is connected to J and define δ = ( δ 1 , δ 2 , . . . , δ n ) ∈ { 0 , 1 } n . Then for every v ∈ { 0 , 1 } n the probability that δ = v is exponentially small. This property holds even if a part of the graph is “frozen.” [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0022247X
- Volume :
- 445
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Journal of Mathematical Analysis & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 118029975
- Full Text :
- https://doi.org/10.1016/j.jmaa.2016.08.020