On "stability" in the Erdös-Ko-Rado Theorem
On "stability" in the Erdös-Ko-Rado Theorem
复制标题
论 Erdös-Ko-Rado 定理中的“稳定性”
DOI：
10.1137/15m1012992
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Kahn
中科院分区：
文献类型：
--
作者：
Pat Devlin;J. Kahn
用$K_p（n，k）$表示通常的Kneser图$K（n，k）$的随机子图，其中每条边独立出现的概率为$p$。通过讨论Bollobas，Narayanan和Raigorodskii的问题，我们证明了存在一个固定的p<1使得a.s. (i.e.,概率趋于1为$k\rightarrow\infty$），$K_p（2k+1，k）$的最大独立集正好是集合$\{A\in V（K（2k+1，k））：x\in A\}$（$x\in [2k+1]$）。我们还完成了上述性质的“阈值”的数量级的确定一般$k$和$n\geq 2k+2$。这对于$k\sim n/2$是新的，而对于较小的$k $，这是Das和Tran最近的结果。
Denote by $K_p(n,k)$ the random subgraph of the usual Kneser graph $K(n,k)$ in which edges appear independently, each with probability $p$. Answering a question of Bollobas, Narayanan, and Raigorodskii, we show that there is a fixed $p<1$ such that a.s. (i.e., with probability tending to 1 as $k\rightarrow\infty$) the maximum independent sets of $K_p(2k+1, k)$ are precisely the sets $\{A\in V(K(2k+1,k)): x\in A\}$ ($x\in [2k+1]$). We also complete the determination of the order of magnitude of the “threshold" for the above property for general $k$ and $n\geq 2k+2$. This is new for $k\sim n/2$, while for smaller $k $ it is a recent result of Das and Tran.