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 class="mathmlsrc">class="formulatext 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,dclass="mathContainer hidden">class="mathCode">${\mathcal{D}}_{n,d}$ be the set of all d-regular directed graphs on n vertices. Let G   be a graph chosen uniformly at random from class="mathmlsrc">class="formulatext 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,dclass="mathContainer hidden">class="mathCode">${\mathcal{D}}_{n,d}$ and M be its adjacency matrix. We show that M   is invertible with probability at least class="mathmlsrc">title="View the MathML source" 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">class="imgLazyJSB inlineImage" height="19" width="106" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0022247X16304292-si2.gif">class="mathContainer hidden">class="mathCode">$1-C{\ln }^{3}d/\sqrt{d}$ for class="mathmlsrc">class="formulatext 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²⁡nclass="mathContainer hidden">class="mathCode">$C\le d\le cn/{\ln }^{2}n$, where class="mathmlsrc">class="formulatext 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,Cclass="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">class="formulatext 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/dclass="mathContainer hidden">class="mathCode">$|J|\approx n/d$. Let class="mathmlsrc">class="formulatext 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">δ_iclass="mathContainer hidden">class="mathCode">${\delta }_i$ be the indicator of the event that the vertex i is connected to J   and define class="mathmlsrc">class="formulatext 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}ⁿclass="mathContainer hidden">class="mathCode">$\delta =({\delta }_1,{\delta }_2,...,{\delta }_n)\in {\{0,1\}}^n$. Then for every class="mathmlsrc">class="formulatext 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}ⁿclass="mathContainer hidden">class="mathCode">$v\in {\{0,1\}}^n$ the probability that class="mathmlsrc">class="formulatext 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">δ=vclass="mathContainer hidden">class="mathCode">$\delta =v$ is exponentially small. This property holds even if a part of the graph is “frozen.”