6533b838fe1ef96bd12a5284
RESEARCH PRODUCT
Adjacency matrices of random digraphs: singularity and anti-concentration
Pierre YoussefKonstantin TikhomirovAnna LytovaNicole Tomczak-jaegermannAlexander E. Litvaksubject
0102 computer and information sciences01 natural scienceslittlewood–offord theory60C05 60B20 05C80 15B52 46B06law.inventionCombinatoricsSingularityanti-concentrationlawFOS: MathematicsMathematics - CombinatoricsAdjacency matrix0101 mathematicsMathematicsinvertibility of random matricesApplied Mathematics010102 general mathematicsProbability (math.PR)random regular graphsDirected graphsingular probabilityGraphVertex (geometry)Invertible matrix010201 computation theory & mathematicsadjacency matricesCombinatorics (math.CO)Mathematics - ProbabilityAnalysisdescription
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".
year | journal | country | edition | language |
---|---|---|---|---|
2017-01-01 |