A simple removal lemma for large nearly-intersecting families

详细信息    查看全文

• 作者：Tuan Tran ^{tuan@math.fu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; Shagnik Das ^{shagnik@mi.fu-berlin.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Erdős-Ko-Rado theorem ; intersecting families ; removal lemma
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：49
• 期：Complete
• 页码：93-99
• 全文大小：218 K

文摘

A k  -uniform family of subsets of [n]$[n]$ is intersecting if it does not contain a disjoint pair of sets. The study of intersecting families is central to extremal set theory, dating back to the seminal Erdős–Ko–Rado theorem of 1961 that bounds the largest such families. A recent trend has been to investigate the structure of set families with few disjoint pairs.

Friedgut and Regev proved a general removal lemma, showing that when $\gamma n\le k\le (\frac{1}{2}-\gamma )n$, a set family with few disjoint pairs can be made intersecting by removing few sets. Our main contribution in this paper is to provide a simple proof of a special case of this theorem, when the family has size close to $\left(\begin{array}{c}\hfill n-1\hfill \\ \hfill k-1\hfill \end{array}\right)$. However, our theorem holds for all $2\le k<\frac{1}{2}n$ and provides sharp quantitative estimates.

We then use this removal lemma to settle a question of Bollobás, Narayanan and Raigorodskii regarding the independence number of random subgraphs of the Kneser graph K(n,k)$K(n,k)$. The Erdős–Ko–Rado theorem shows $\alpha (K(n,k))=\left(\begin{array}{c}\hfill n-1\hfill \\ \hfill k-1\hfill \end{array}\right)$. For some constant c>0$c>0$ and k≤cn$k\le cn$, we determine the sharp threshold for when this equality holds for random subgraphs of K(n,k)$K(n,k)$, and provide strong bounds on the critical probability for $k\le \frac{1}{2}(n-3)$.