Dense random regular digraphs: singularity of the adjacency matrix

Abstract

Fix $c\in (0,1)$ and let $\Gamma$ be a $\lfloor cn\rfloor$-regular digraph on $n$ vertices drawn uniformly at random. We prove that when $n$ is large, the (non-symmetric) adjacency matrix $M$ of $\Gamma$ is invertible with high probability. The proof uses a couplings approach based on the switchings method of McKay and Wormald. We also rely on discrepancy properties for the distribution of edges in $\Gamma$, recently proved by the author, to overcome certain difficulties stemming from the dependencies between the entries of $M$.

The paper has been withdrawn by the author as it is superseded by arXiv:1411.0243

References in corpus (1)

• Circular law for random matrices with exchangeable entries