کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4613999 | 1339277 | 2017 | 45 صفحه PDF | دانلود رایگان |
Let Dn,dDn,d be the set of all d-regular directed graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,dDn,d and M be its adjacency matrix. We show that M is invertible with probability at least 1−Cln3d/d for C≤d≤cn/ln2nC≤d≤cn/ln2n, where c,Cc,C are positive absolute constants. To this end, we establish a few properties of d-regular directed graphs. One of them, a Littlewood–Offord type anti-concentration property, is of independent interest. Let J be a subset of vertices of G with |J|≈n/d|J|≈n/d. Let δiδi be the indicator of the event that the vertex i is connected to J and define δ=(δ1,δ2,...,δn)∈{0,1}nδ=(δ1,δ2,...,δn)∈{0,1}n. Then for every v∈{0,1}nv∈{0,1}n the probability that δ=vδ=v is exponentially small. This property holds even if a part of the graph is “frozen.”
Journal: Journal of Mathematical Analysis and Applications - Volume 445, Issue 2, 15 January 2017, Pages 1447–1491