On the stability of some Erdős-Ko-Rado type results

详细信息    查看全文

• 作者：M.M. Pyaderkin ; ^{meshanya@gmail.com}
• 关键词：Random graph ; Kneser graph ; Intersecting family ; Erdős&ndash ; Ko&ndash ; Rado theorem
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：340
• 期：4
• 页码：822-831
• 全文大小：439 K
• 卷排序：340

文摘

Consider classical Kneser’s graph K(n,r)K(n,r): for two natural numbers r,nr,n such that r⩽n∕2r⩽n∕2, its vertices are all the subsets of [n]={1,2,…,n}[n]={1,2,…,n} of size rr, and two such vertices are adjacent if the corresponding subsets are disjoint. The Erdős–Ko–Rado theorem states that the size of the largest independent set in this graph is n−1r−1. Now let us delete each edge of the graph K(n,r)K(n,r) with some fixed probability pp independently of each other. Quite surprisingly, the independence number of such random subgraph Kp(n,r)Kp(n,r) of the graph K(n,r)K(n,r) is, with high probability, the same as the independence number of the initial graph. This phenomenon is called the stability of the independence number. This paper concerns the independence number of random subgraphs of the graph G(n,r,1)G(n,r,1), which vertices are the same as in the Kneser graph and there is an edge between two vertices if they intersect in exactly one element. We prove the stability result for constant rr and p=12. To do that, we show that any sufficiently large independent set in G(n,r,1)G(n,r,1) has some predefined structure, and this is a result of independent interest.