论文标题
随机图的独立数的两点浓度
Two-Point Concentration of the Independence Number of the Random Graph
论文作者
论文摘要
我们表明，如果$ n^{ - 2/3+ε} <p \ le 1 $，$ g_ {n，p} $的独立数集中在两个值上。当SAH和Sawhney的参数表明独立号通常不集中于$ p = o \ left的2个值（（（\ log（n）/n）/n）^{2/3} \ right）$的2个值。 $ g_ {n，p} $的独立性浓度的程度，对于$ω（1/n）<p \ le n^{ - 2/3} $仍然是一个有趣的开放问题。
We show that the independence number of $ G_{n,p}$ is concentrated on two values if $ n^{-2/3+ ε} < p \le 1$. This result is roughly best possible as an argument of Sah and Sawhney shows that the independence number is not, in general, concentrated on 2 values for $ p = o \left( (\log(n)/n)^{2/3} \right)$. The extent of concentration of the independence number of $ G_{n,p}$ for $ ω(1/n) <p \le n^{-2/3}$ remains an interesting open question.
