Adjacency matrices of random digraphs: singularity and anti-concentration

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

48 citations recorded by the source corpus.

Let ${\mathcal 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 ${\mathcal D}_{n,d}$ and $M$ be its adjacency matrix. We show that $M$ is invertible with probability at least $1-C\ln^{3} d/\sqrt{d}$ for $C\leq d\leq cn/\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|\approx n/d$. Let $\delta_i$ be the indicator of the event that the vertex $i$ is connected to $J$ and define $\delta = (\delta_1, \delta_2, ..., \delta_n)\in \{0, 1\}^n$. Then for every $v\in\{0,1\}^n$ the probability that $\delta=v$ is exponentially small. This property holds even if a part of the graph is "frozen".

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/3a07f530e0fa57d52e2f23e004fd7ac23682b52f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

  1. Konstantin E. Tikhomirov
  2. Pierre Youssef

In Geometry and Topology

  1. Konstantin E. Tikhomirov
  2. Pierre Youssef

In Statistics and Probability

  1. Konstantin E. Tikhomirov
  2. Pierre Youssef

Citations in the corpus