화학공학소재연구정보센터
SIAM Journal on Control and Optimization, Vol.54, No.6, 3347-3378, 2016
ON A CONJECTURE OF GODSIL CONCERNING CONTROLLABLE RANDOM GRAPHS
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].