Anti-concentration property for random digraphs and invertibility of their adjacency matrices

Alexander E. Litvak; Anna Lytova; Konstantin Tikhomirov; Nicole Tomczak-Jaegermann; Pierre Youssef

doi:10.1016/j.crma.2015.12.002

Anti-concentration property for random digraphs and invertibility of their adjacency matrices

Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

Let Dn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,d and M be its adjacency matrix. We show that M is invertible with probability at least 1-Cln³d/d for C≤d≤cn/ln²n, where c, C are positive absolute constants. To this end, we establish a few properties of directed d-regular 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|≤cn/d. Let δ_i be the indicator of the event that the vertex i is connected to J and δ=(δ₁, δ₂, . ., δ_n)∈[0, 1]ⁿ. Then δ is not concentrated around any vertex of the cube. This property holds even if a part of the graph is fixed.

Original language	English (US)
Pages (from-to)	121-124
Number of pages	4
Journal	Comptes Rendus Mathematique
Volume	354
Issue number	2
DOIs	https://doi.org/10.1016/j.crma.2015.12.002
State	Published - Feb 1 2016

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1016/j.crma.2015.12.002

Cite this

@article{edd272b3a2c24360b22a22e2522bb8da,

title = "Anti-concentration property for random digraphs and invertibility of their adjacency matrices",

abstract = "Let Dn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,d and M be its adjacency matrix. We show that M is invertible with probability at least 1-Cln3d/d for C≤d≤cn/ln2n, where c, C are positive absolute constants. To this end, we establish a few properties of directed d-regular 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|≤cn/d. Let δi be the indicator of the event that the vertex i is connected to J and δ=(δ1, δ2, . ., δn)∈[0, 1]n. Then δ is not concentrated around any vertex of the cube. This property holds even if a part of the graph is fixed.",

author = "Litvak, {Alexander E.} and Anna Lytova and Konstantin Tikhomirov and Nicole Tomczak-Jaegermann and Pierre Youssef",

note = "Publisher Copyright: {\textcopyright} 2015 Acad{\'e}mie des sciences.",

year = "2016",

month = feb,

day = "1",

doi = "10.1016/j.crma.2015.12.002",

language = "English (US)",

volume = "354",

pages = "121--124",

journal = "Comptes Rendus Mathematique",

issn = "1631-073X",

publisher = "Academie des sciences",

number = "2",

}

TY - JOUR

T1 - Anti-concentration property for random digraphs and invertibility of their adjacency matrices

AU - Litvak, Alexander E.

AU - Lytova, Anna

AU - Tikhomirov, Konstantin

AU - Tomczak-Jaegermann, Nicole

AU - Youssef, Pierre

PY - 2016/2/1

Y1 - 2016/2/1

N2 - Let Dn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,d and M be its adjacency matrix. We show that M is invertible with probability at least 1-Cln3d/d for C≤d≤cn/ln2n, where c, C are positive absolute constants. To this end, we establish a few properties of directed d-regular 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|≤cn/d. Let δi be the indicator of the event that the vertex i is connected to J and δ=(δ1, δ2, . ., δn)∈[0, 1]n. Then δ is not concentrated around any vertex of the cube. This property holds even if a part of the graph is fixed.

AB - Let Dn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,d and M be its adjacency matrix. We show that M is invertible with probability at least 1-Cln3d/d for C≤d≤cn/ln2n, where c, C are positive absolute constants. To this end, we establish a few properties of directed d-regular 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|≤cn/d. Let δi be the indicator of the event that the vertex i is connected to J and δ=(δ1, δ2, . ., δn)∈[0, 1]n. Then δ is not concentrated around any vertex of the cube. This property holds even if a part of the graph is fixed.

UR - http://www.scopus.com/inward/record.url?scp=84956845390&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84956845390&partnerID=8YFLogxK

U2 - 10.1016/j.crma.2015.12.002

DO - 10.1016/j.crma.2015.12.002

M3 - Article

AN - SCOPUS:84956845390

SN - 1631-073X

VL - 354

SP - 121

EP - 124

JO - Comptes Rendus Mathematique

JF - Comptes Rendus Mathematique

IS - 2

ER -

Anti-concentration property for random digraphs and invertibility of their adjacency matrices

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this