On the stability of the Erdős-Ko-Rado theorem
On the stability of the Erdős-Ko-Rado theorem
复制标题
关于 Erdős-Ko-Rado 定理的稳定性
DOI：
10.1016/j.jcta.2015.08.002
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Raigorodskii
中科院分区：
文献类型：
--
作者：
B. Bollobás;Bhargav P. Narayanan;A. Raigorodskii
以一定的概率删除Kneser图的边：在多大的概率下，这个随机图的独立数等于Kneser图本身的独立数？我们证明了这个问题在某些制度的一个尖锐的阈值结果。由于Kneser图中的独立集与相交（一致）族相同，这给了我们一个Erdens-Ko-Rado定理的随机模拟。
Delete the edges of a Kneser graph independently of each other with some probability: for what probabilities is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as an intersecting (uniform) family, this gives us a random analogue of the Erdős–Ko–Rado theorem.