TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM
TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM
复制标题
ErdŐS-KO-RADO 定理的传递
DOI：
10.1017/fms.2015.21
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Bhargav P. Narayanan
中科院分区：
文献类型：
--
作者：
J. Balogh;B. Bollobás;Bhargav P. Narayanan
对于自然数$n，r\in \mathbb{N}$且$n\geqslant r$，Kneser图$K（n，r）$是$\{1，\ldots，n\}$的$r$-元子集族上的图，其中两个集合相邻当且仅当它们不相交。以一定的概率删除$K（n，r）$的边，并且这些边彼此独立：这个随机图的独立数是否等于Kneser图本身的独立数？我们将肯定地回答这个问题，只要$r/n$有界远离$1/2$，即使当保留Kneser图的边的概率很小。这给了我们一个随机的类似的Erdens-Ko-Rado定理，因为在Kneser图中的一个独立集是相同的一致相交的家庭。为了证明我们的主要结果，我们给出了一些新的估计的数量不相交对在一个家庭的距离从一个相交的家庭，这些可能是独立的利益。
For natural numbers $n,r\in \mathbb{N}$ with $n\geqslant r$, the Kneser graph $K(n,r)$ is the graph on the family of $r$-element subsets of $\{1,\ldots ,n\}$ in which two sets are adjacent if and only if they are disjoint. Delete the edges of $K(n,r)$ with some probability, independently of each other: is the independence number of this random graph equal to the independence number of the Kneser graph itself? We shall answer this question affirmatively as long as $r/n$ is bounded away from $1/2$, even when the probability of retaining an edge of the Kneser graph is quite small. This gives us a random analogue of the Erdős–Ko–Rado theorem, since an independent set in the Kneser graph is the same as a uniform intersecting family. To prove our main result, we give some new estimates for the number of disjoint pairs in a family in terms of its distance from an intersecting family; these might be of independent interest.