• ### Lower bounds for the smallest singular value of structured random matrices(1608.07347)

May 18, 2018 math.PR
We obtain lower tail estimates for the smallest singular value of random matrices with independent but non-identically distributed entries. Specifically, we consider $n\times n$ matrices with complex entries of the form $M = A\circ X + B = (a_{ij}\xi_{ij} + b_{ij})$ where $X=(\xi_{ij})$ has iid centered entries of unit variance and $A$ and $B$ are fixed matrices. In our main result we obtain polynomial bounds on the smallest singular value of $M$ for the case that $A$ has bounded (possibly zero) entries, and $B= Z\sqrt{n}$ where $Z$ is a diagonal matrix with entries bounded away from zero. As a byproduct of our methods we can also handle general perturbations $B$ under additional hypotheses on $A$, which translate to connectivity hypotheses on an associated graph. In particular, we extend a result of Rudelson and Zeitouni for Gaussian matrices to allow for general entry distributions satisfying some moment hypotheses. Our proofs make use of tools which (to our knowledge) were previously unexploited in random matrix theory, in particular Szemer\'edi's Regularity Lemma, and a version of the Restricted Invertibility Theorem due to Spielman and Srivastava.
• ### The circular law for random regular digraphs with random edge weights(1508.00208)

Sept. 8, 2017 math.PR
We consider random $n\times n$ matrices of the form $Y_n=\frac1{\sqrt{d}}A_n\circ X_n$, where $A_n$ is the adjacency matrix of a uniform random $d$-regular directed graph on $n$ vertices, with $d=\lfloor p n\rfloor$ for some fixed $p \in (0,1)$, and $X_n$ is an $n\times n$ matrix of iid centered random variables with unit variance and finite $4+\eta$-th moment (here $\circ$ denotes the matrix Hadamard product). We show that as $n\to \infty$, the empirical spectral distribution of $Y_n$ converges weakly in probability to the normalized Lebesgue measure on the unit disk.
• ### The circular law for random regular digraphs(1703.05839)

Aug. 7, 2017 math.CO, math.PR
Let $\log^Cn\le d\le n/2$ for a sufficiently large constant $C>0$ and let $A_n$ denote the adjacency matrix of a uniform random $d$-regular directed graph on $n$ vertices. We prove that as $n$ tends to infinity, the empirical spectral distribution of $A_n$, suitably rescaled, is governed by the Circular Law. A key step is to obtain quantitative lower tail bounds for the smallest singular value of additive perturbations of $A_n$.
• ### Size biased couplings and the spectral gap for random regular graphs(1510.06013)

March 8, 2017 math.CO, math.PR
Let $\lambda$ be the second largest eigenvalue in absolute value of a uniform random $d$-regular graph on $n$ vertices. It was famously conjectured by Alon and proved by Friedman that if $d$ is fixed independent of $n$, then $\lambda=2\sqrt{d-1} +o(1)$ with high probability. In the present work we show that $\lambda=O(\sqrt{d})$ continues to hold with high probability as long as $d=O(n^{2/3})$, making progress towards a conjecture of Vu that the bound holds for all $1\le d\le n/2$. Prior to this work the best result was obtained by Broder, Frieze, Suen and Upfal (1999) using the configuration model, which hits a barrier at $d=o(n^{1/2})$. We are able to go beyond this barrier by proving concentration of measure results directly for the uniform distribution on $d$-regular graphs. These come as consequences of advances we make in the theory of concentration by size biased couplings. Specifically, we obtain Bennett-type tail estimates for random variables admitting certain unbounded size biased couplings.
• ### On the singularity of adjacency matrices for random regular digraphs(1411.0243)

Nov. 9, 2015 math.CO, math.PR
We prove that the (non-symmetric) adjacency matrix of a uniform random $d$-regular directed graph on $n$ vertices is asymptotically almost surely invertible, assuming $\min(d,n-d)\ge C\log^2n$ for a sufficiently large constant $C>0$. The proof makes use of a coupling of random regular digraphs formed by "shuffling" the neighborhood of a pair of vertices, as well as concentration results for the distribution of edges recently obtained by the author (arXiv:1410.5595). We also apply our general approach to prove a.a.s.\ invertibility of Hadamard products $\Sigma\circ \Xi$, where $\Xi$ is a matrix of iid uniform $\pm1$ signs, and $\Sigma$ is a 0/1 matrix whose associated digraph satisfies certain "expansion" properties.
• ### Discrepancy properties for random regular digraphs(1410.5595)

Oct. 26, 2015 math.CO, math.PR
For the uniform random regular directed graph we prove concentration inequalities for (1) codegrees and (2) the number of edges passing from one set of vertices to another. As a consequence, we can deduce discrepancy properties for the distribution of edges essentially matching results for Erd\H{o}s-R\'enyi digraphs obtained from Chernoff-type bounds. The proofs make use of the method of exchangeable pairs, developed for concentration of measure by Chatterjee. Exchangeable pairs are constructed using two involutions on the set of regular digraphs: a well-known "simple switching" operation, as well as a novel "reflection" operation.
• ### Dense random regular digraphs: singularity of the adjacency matrix(1403.5845)

Aug. 2, 2015 math.CO, math.PR
Fix $c\in (0,1)$ and let $\Gamma$ be a $\lfloor c n\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$.