Godsil's controllability conjecture for random graphs

Let G(n,1/2)G(n,1/2) be the Erdős–Rényi random graph on nn vertices, and let GG 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)G(n,1/2) is controllable and minimally controllable approaches 11 as nn\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.

Sources & referencesView supporting material

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.

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.

Solutions 0

No solutions have been posted yet.