论文标题
Seymour的第二个社区猜想（伪）随机图的方向
Seymour's Second Neighborhood Conjecture for orientations of (pseudo)random graphs
论文作者
论文摘要
西摩的第二个社区猜想（SNC）指出，每个方向的图都包含一个顶点，其第二个社区与第一个社区一样大。我们研究了SNC的二项式和伪随机图的方向，几乎可以毫无疑问地（A.A.S.）对SNC进行验证（A.A.S.） （i）对于$ g（n，p）$的所有方向，如果$ \ limsup_ {n \ to \ infty} p <1/4 $;和 (ii) for a uniformly-random orientation of each weakly $(p,A\sqrt{np})$-bijumbled graph of order $n$ and density $p$, where $p=Ω(n^{-1/2})$ and $1-p = Ω(n^{-1/6})$ and $A>0$ is a universal constant independent of both $n$ and $p$. 我们还表明A.A.S. SNC几乎以$ g（n，p）$的所有方向持有。更具体地说，我们证明了A.A.S. （iii）对于所有$ \ varepsilon> 0 $和$ p = p = p（n）$，带有$ \ limsup_ {n \ to \ infty} p \ le 2/3- \ varepsilon $，$ g（n，p）$的每一个方向都以最小的ofdeg $ f varepsilon（n，p）满足snc $ snc $ nc \ sq \ sqrt;和 （iv）对于所有$ p = p（n）$，$ g（n，p）$的随机方向满足SNC。
Seymour's Second Neighborhood Conjecture (SNC) states that every oriented graph contains a vertex whose second neighborhood is as large as its first neighborhood. We investigate the SNC for orientations of both binomial and pseudo random graphs, verifying the SNC asymptotically almost surely (a.a.s.) (i) for all orientations of $G(n,p)$ if $\limsup_{n\to\infty} p < 1/4$; and (ii) for a uniformly-random orientation of each weakly $(p,A\sqrt{np})$-bijumbled graph of order $n$ and density $p$, where $p=Ω(n^{-1/2})$ and $1-p = Ω(n^{-1/6})$ and $A>0$ is a universal constant independent of both $n$ and $p$. We also show that a.a.s. the SNC holds for almost every orientation of $G(n,p)$. More specifically, we prove that a.a.s. (iii) for all $\varepsilon > 0$ and $p=p(n)$ with $\limsup_{n\to\infty} p \le 2/3-\varepsilon$, every orientation of $G(n,p)$ with minimum outdegree $Ω_\varepsilon(\sqrt{n})$ satisfies the SNC; and (iv) for all $p=p(n)$, a random orientation of $G(n,p)$ satisfies the SNC.
