Adjacency matrices of random digraphs: Singularity and anti-concentration

详细信息    查看全文

• 作者：Alexander E. Litvak^a ; ^{aelitvak@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Anna Lytova^a ; ^{lytova@ualberta.ca" class="auth_mail" title="E-mail the corresponding author} ; Konstantin Tikhomirov^a ; ^{ktikhomi@ualberta.ca" class="auth_mail" title="E-mail the corresponding author} ; Nicole Tomczak-Jaegermann^a ; ^{nicole.tomczak@ualberta.ca" class="auth_mail" title="E-mail the corresponding author} ; Pierre Youssef^b ; ^{youssef@math.univ-paris-diderot.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Adjacency matrices ; Anti-concentration ; Invertibility of random matrices ; Littlewood&ndash ; Offord theory ; Random regular graphs ; Singular probability
• 刊名：Journal of Mathematical Analysis and Applications
• 出版年：2017
• 出版时间：15 January 2017
• 年：2017
• 卷：445
• 期：2
• 页码：1447-1491
• 全文大小：760 K

文摘

Let rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si1.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=bcf6daf0c72f617385d3e9f502c71afe" title="Click to view the MathML source">D_n,dr hidden">roll">row>riant="script">Drow>row>n,drow> be the set of all d-regular directed graphs on n vertices. Let G   be a graph chosen uniformly at random from rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si1.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=bcf6daf0c72f617385d3e9f502c71afe" title="Click to view the MathML source">D_n,dr hidden">roll">row>riant="script">Drow>row>n,drow> and M be its adjacency matrix. We show that M   is invertible with probability at least rc">rce" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si2.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=a0d19eb1518f406e6cb7e5feb3cb6628">rce" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0022247X16304292-si2.gif">ript>rder="0" style="vertical-align:bottom" width="106" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0022247X16304292-si2.gif">ript>r hidden">roll">1−Crow>riant="normal">lnrow>row>3row>⁡dretchy="false">/rt>drt> for rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si3.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=3fdcf4b237f38a12c96660b915da6a47" title="Click to view the MathML source">C≤d≤cn/ln²⁡nr hidden">roll">C≤d≤cnretchy="false">/row>riant="normal">lnrow>row>2row>⁡n, where rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si34.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=b5560005cc22ac8677d8c035c46937a7" title="Click to view the MathML source">c,Cr hidden">roll">c,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 rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si5.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=44c1abf510306ce89c565df3b4c8c253" title="Click to view the MathML source">|J|≈n/dr hidden">roll">retchy="false">|Jretchy="false">|≈nretchy="false">/d. Let rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si6.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=62d15519ed69bbf88f2e8224f9fb6281" title="Click to view the MathML source">δ_ir hidden">roll">row>δrow>row>irow> be the indicator of the event that the vertex i is connected to J   and define rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si7.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=8c5d6f89fcf07fe0d43cc44ff34081dc" title="Click to view the MathML source">δ=(δ₁,δ₂,...,δ_n)∈{0,1}ⁿr hidden">roll">δ=retchy="false">(row>δrow>row>1row>,row>δrow>row>2row>,...,row>δrow>row>nrow>retchy="false">)∈row>retchy="false">{0,1retchy="false">}row>row>nrow>. Then for every rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si104.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=0522eac2a64dbac1b96a18423143d105" title="Click to view the MathML source">v∈{0,1}ⁿr hidden">roll">v∈row>retchy="false">{0,1retchy="false">}row>row>nrow> the probability that rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16304292&_mathId=si9.gif&_user=111111111&_pii=S0022247X16304292&_rdoc=1&_issn=0022247X&md5=6fd1fda915dcc8f8d7cbe68043fc20e7" title="Click to view the MathML source">δ=vr hidden">roll">δ=v is exponentially small. This property holds even if a part of the graph is “frozen.”