Adjacency matrices of random digraphs: Singularity and anti-concentration

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

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

Let Dn,d be the set of all d-regular directed 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−Cln3⁡d/d for C≤d≤cn/ln2⁡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 δ=(δ12,…,δ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.”

Original languageEnglish (US)
Pages (from-to)1447-1491
Number of pages45
JournalJournal of Mathematical Analysis and Applications
Volume445
Issue number2
DOIs
StatePublished - Jan 15 2017

All Science Journal Classification (ASJC) codes

  • Analysis
  • Applied Mathematics

Keywords

  • Adjacency matrices
  • Anti-concentration
  • Invertibility of random matrices
  • Littlewood–Offord theory
  • Random regular graphs
  • Singular probability

Fingerprint Dive into the research topics of 'Adjacency matrices of random digraphs: Singularity and anti-concentration'. Together they form a unique fingerprint.

Cite this