The nonsingularity conjecture for random regular graph adjacency matrices

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 1

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).

Sources & referencesView supporting material

Primary source

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

1 week ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

No solutions have been posted yet.

Equivalent formulations 1

Nonsingularity conjecture for random regular graph adjacency matrices

Primary source

Progress summary