Godsil's controllability conjecture for random graphs

About 11 years old · traced to 2015

Let $G(n,1/2)$ be the Erdős–Rényi random graph on $n$ vertices, and let $G$ be controllable and minimally controllable when it has the corresponding controllability properties for its adjacency matrix. Godsil's conjecture. The probability that $G(n,1/2)$ is controllable and minimally controllable approaches $1$ as $n\to\infty$ . This conjecture concerns the typical controllability of simple graphs; the source states that it was recently proven, so it is no longer open.

References

Primary source

Sean O'Rourke and Philip Matchett Wood, “Low-degree factors of random polynomials”, arXiv:1608.01938 (2018).

Additional references

2 papers in this index state this conjecture (2015–2016). The statement above is taken from the most recent of them; the others are arXiv:1511.05080.

Posted 1 month ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed solved

Two papers from 2015 report proofs that random graphs almost surely have both controllability properties, but this report does not independently verify those proofs.

Godsil’s conjecture says that, as the number of vertices grows, almost every Erdős–Rényi random graph has both ordinary and minimal controllability.

2015 reported proofs

A June 2015 paper reports a stronger result: for fixed edge probability, every single-vertex input is controllable with probability tending to one, which implies minimal controllability for edge probability $1/2$ . A November 2015 paper reports that $(A_n,\mathbf{1}_n)$ is controllable with probability at least $1-Cn^{-\alpha}$ for every $\alpha>0$ , proving the original controllability assertion for $G(n,1/2)$ . A 2016 catalogue source describes the conjecture as recently proven.

Current status (as of September 2026): The conjecture is reported as proved by 2015 papers, including both controllability and minimal controllability, but those proofs remain unverified in this report.

Sources

No solutions have been posted yet.