The nonsingularity conjecture for random regular graph adjacency matrices

About 6 years old · traced to 2020

Let $G_{n,d}$ be a uniformly random simple $d$ -regular graph on $n$ vertices, and let $A_{n,d}$ be its adjacency matrix.

Random regular graph singularity conjecture. For every $3\leq d\leq n-1$ , $A_{n,d}$ is nonsingular with probability $1-o(1)$ .

The conjecture was raised by Vu and later appeared in work of Frieze and Vu. The source reports that the symmetric case has since been solved, so this conjecture is solved.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Nonsingularity conjecture for random regular graph adjacency matrices
Let $Q_{n,d}$ be the adjacency matrix of a uniformly random simple $d$ -regular graph on $n$ vertices. Random regular nonsingularity conjecture. For every $d\ge 3$ , $Q_{n,d}$ is almost surely nonsingular. The source contrasts this with the case $d=2$ , where the adjacency matrix is almost surely singular because the graph is a union of cycles. No resolution is supplied for the stated range $d\ge3$ .
source: V. Vu, “Random Discrete Matrices”, arXiv:math/0611321 (2006).

References

Primary source

Van Vu, “Recent progress in combinatorial random matrix theory”, arXiv:2005.02797 (2020).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

The conjecture is reported settled for all allowed degrees, although the exact rate of the rare failures is still unknown.

Vu raised the conjecture, later recorded by Frieze and Vu in 2014: a uniformly random simple regular graph should have a nonsingular adjacency matrix with probability tending to one.

Known results

Huang (2018): for fixed $d\geq 3$ , the singularity probability is at most $n^{-c}$ , with $c=\min\{1/8,(d-2)/(5d-6)\}$ .
Landon, Sose, and Yau: the symmetric case for $d\geq n^c$ was proved for every fixed $c>0$ .
Mészáros and Huang: the remaining fixed-degree symmetric case was solved.
The sharp decay exponent remains unknown; a lower bound has order $n^{-d+2}$ .

Reported completion, 2020

Huang’s 2020 survey reports that the fixed- and large-degree results together settle the symmetric random-regular-graph conjecture. This is a reported theorem-level resolution, but the retrieved record supplies no independent verification assessment.

Current status (as of September 2026): The conjecture is reported settled for all $3\leq d\leq n-1$ , while the sharp singularity-probability exponent remains open.

Sources

No solutions have been posted yet.

Nonsingularity conjecture for random regular graph adjacency matrices

Primary source

Progress summary