Name
Abstract | ||
|---|---|---|
It is conjectured by Godsil [Anna. Comb., 16 (2012), pp. 733-744] that the relative number of controllable graphs compared to the total number of simple graphs on n vertices approaches one as n tends to infinity. We prove that this conjecture is true. More generally, our methods show that the linear system formed from the pair (W, b) is controllable for a large class of Wigner random matrices W and deterministic vectors b. The proof relies on recent advances in Littlewood-Offord theory developed by Rudelson and Vershynin [Geom. Funct. Anal., to appear; at Adv. Math., 218 (2008), 600-633] and [R. Vershynin, Random Structures Algorithms, 44 (2014), 135-182]. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1137/15M1049622 | SIAM JOURNAL ON CONTROL AND OPTIMIZATION |
Keywords | Field | DocType |
controllability,random matrices,controllable graphs,Littlewood-Offord theory | Discrete mathematics,Graph,Mathematical optimization,Combinatorics,Random graph,Linear system,Vertex (geometry),Infinity,Conjecture,Mathematics,Random matrix | Journal |
Volume | Issue | ISSN |
54 | 6 | 0363-0129 |
Citations | PageRank | References |
1 | 0.36 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| s f c orourke | 1 | 1 | 0.36 |
| Behrouz Touri | 2 | 176 | 21.12 |