The singularity probability of dense random regular graphs
Zeyan SongHanchao WangShengyan YinKexin Yu
所有作者
Zeyan SongHanchao WangShengyan YinKexin Yu
文献摘要
Let Gn,d be a uniformly random simple d-regular graph on n vertices, and let An be its adjacency matrix. For every fixed λ∈(0,1/2), we prove that for any λ(n−1)≤d≤(1−λ)(n−1), P(An is singular)≤e−cn, where c>0 depends only on λ, and n is sufficiently large with nd even.