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

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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)121-124
Number of pages4
JournalComptes Rendus Mathematique
Issue number2
StatePublished - Feb 1 2016

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Anti-concentration property for random digraphs and invertibility of their adjacency matrices'. Together they form a unique fingerprint.

Cite this