刊名: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">Dn,dclass="mathContainer hidden">class="mathCode"> 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">Dn,dclass="mathContainer hidden">class="mathCode"> 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"> 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/ln2nclass="mathContainer hidden">class="mathCode">, 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"> 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">. 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"> 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">δ=(δ1,δ2,...,δn)∈{0,1}nclass="mathContainer hidden">class="mathCode">. 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}nclass="mathContainer hidden">class="mathCode"> 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"> is exponentially small. This property holds even if a part of the graph is “frozen.”