Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper analyzes the singularity probability of adjacency matrices for dense random regular graphs $G_{n,d}$. For a fixed $\lambda \in (0, 1/2)$, it establishes an exponential decay in singularity probability ($e^{-cn}$) for $d$ in the range $\lambda(n-1) \le d \le (1-\lambda)(n-1)$, provided $nd$ is even and $n$ is sufficiently large. This result provides a precise bound on the likelihood of a random regular graph's adjacency matrix being singular in dense regimes.
Dense random regular graphs are almost surely non-singular for a wide range of degrees.
Let $G_{n,d}$ be a uniformly random simple $d$-regular graph on $n$ vertices, and let $A_n$ be its adjacency matrix. For every fixed $\lambda\in(0,1/2)$, we prove that for any $\lambda(n-1)\le d\le(1-\lambda)(n-1)$, $\mathbb P(A_n\text{ is singular})\le e^{-cn}$, where $c>0$ depends only on $\lambda$, and $n$ is sufficiently large with $nd$ even.