Sharp threshold for the Erdős–Ko–Rado theorem
Sharp threshold for the Erdős–Ko–Rado theorem
复制标题
ErdÅsâKoâRado 定理的尖锐阈值
DOI：
10.1002/rsa.21090
复制
发表时间：
2023
影响因子：
1
通讯作者：
Luo, Haoran
中科院分区：
文献类型：
--
作者：
Balogh, József;Krueger, Robert A.;Luo, Haoran
对于正整数n$$ n $$和k$$ k $$且n≥2k+1$$ n\ge 2k+1 $$，Kneser图K（n，k）$$ K\left（n，k\right）$$是顶点集由{1，.，n}$$ \left\{1，\dots，n\right\} $$的所有k$$ k $-集组成的图，其中两个k$$ k $$-集在不相交时恰好相邻。K（n，k）$$ K\left（n，k\right）$$的独立集是k$$ k $$-一致相交族，因此最大大小的独立集由Erdens-Ko-Rado定理给出。设Kp（n，k）$$ {K}_p\left（n，k\right）$$是K（n，k）$$ K\left（n，k\right）$$的一个随机生成子图，其中每条边以概率p$$ p $$独立包含。Bollobás、Narayanan和Raigorodskii问了一个问题，即Kp（n，k）$$ {K}_p\left（n，k\right）$$与K（n，k）$$ K\left（n，k\right）$$具有相同独立数的概率是多少。对于n=2k+1$$ n=2k+1 $$，我们证明了一个命中时间结果，它给出了这个问题在p=3/4$$ p=3/4 $$的一个尖锐的阈值。此外，在完成Das和Tran以及Devlin和Kahn的工作的基础上，我们对所有n>2k+1$$ n>2k+1 $$确定了一个尖锐的阈值函数。
For positive integers n$$ n $$ and k$$ k $$ with n≥2k+1$$ n\ge 2k+1 $$, the Kneser graph K(n,k)$$ K\left(n,k\right) $$ is the graph with vertex set consisting of all k$$ k $$‐sets of {1,…,n}$$ \left\{1,\dots, n\right\} $$, where two k$$ k $$‐sets are adjacent exactly when they are disjoint. The independent sets of K(n,k)$$ K\left(n,k\right) $$ are k$$ k $$‐uniform intersecting families, and hence the maximum size independent sets are given by the Erdős–Ko–Rado Theorem. Let Kp(n,k)$$ {K}_p\left(n,k\right) $$ be a random spanning subgraph of K(n,k)$$ K\left(n,k\right) $$ where each edge is included independently with probability p$$ p $$. Bollobás, Narayanan, and Raigorodskii asked for what p$$ p $$ does Kp(n,k)$$ {K}_p\left(n,k\right) $$ have the same independence number as K(n,k)$$ K\left(n,k\right) $$ with high probability. For n=2k+1$$ n=2k+1 $$, we prove a hitting time result, which gives a sharp threshold for this problem at p=3/4$$ p=3/4 $$. Additionally, completing work of Das and Tran and work of Devlin and Kahn, we determine a sharp threshold function for all n>2k+1$$ n>2k+1 $$.
登录
查看更多内容
论随机超图 II 的 Erdős–Ko–Rado
DOI：
10.1017/s0963548318000433
发表时间：
2014
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
Arran Hamm;J. Kahn
通讯作者：
J. Kahn
随机超图中的 Erdős–Ko–Rado
DOI：
10.1017/s0963548309990253
发表时间：
2009
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
J. Balogh;T. Bohman;D. Mubayi
通讯作者：
D. Mubayi
离散结构的相交族通常是微不足道的
DOI：
10.1016/j.jcta.2015.01.003
发表时间：
2014
期刊：
J. Comb. Theory A
影响因子：
--
作者：
J. Balogh;Shagnik Das;Michelle Delcourt;Hong Liu;M. Sharifzadeh
通讯作者：
M. Sharifzadeh
ErdŐS-KO-RADO 定理的传递
DOI：
10.1017/fms.2015.21
发表时间：
2015
期刊：
Forum of Mathematics, Sigma
影响因子：
--
作者：
J. Balogh;B. Bollobás;Bhargav P. Narayanan
通讯作者：
Bhargav P. Narayanan
论 Erdös-Ko-Rado 定理中的“稳定性”
DOI：
10.1137/15m1012992
发表时间：
2015
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
Pat Devlin;J. Kahn
通讯作者：
J. Kahn