On set systems without a simplex-cluster and the Junta method

Abstract

A family $\{A_0,\dots ,A_d\}$ of $k$-element subsets of $[n]=\{1,2,\dots ,n\}$ is called a simplex-cluster if $A_0\cap \cdots \cap A_d=\varnothing$, $|A_0\cup \cdots \cup A_d|\le 2k$, and the intersection of any $d$ of the sets in $\{A_0,\dots ,A_d\}$ is nonempty. In 2006, Keevash and Mubayi conjectured that for any $d+1\le k\le \frac{d}{d+1}n$, the largest family of $k$-element subsets of $[n]$ that does not contain a simplex-cluster is the family of all $k$-subsets that contain a given element. We prove the conjecture for all $k\ge \zeta n$ for an arbitrarily small $\zeta >0$, provided that $n\ge n_0(\zeta ,d)$. We call a family $\{A_0,\dots ,A_d\}$ of $k$-element subsets of $[n]$ a $(d,k,s)$-cluster if $A_0\cap \cdots \cap A_d=\varnothing$ and $|A_0\cup \cdots \cup A_d|\le s$. We also show that for any $\zeta n\le k\le \frac{d}{d+1}n$ the largest family of $k$-element subsets of $[n]$ that does not contain a $(d,k,(\frac{d+1}{d}+\zeta )k)$-cluster is again the family of all $k$-subsets that contain a given element, provided that $n\ge n_0(\zeta ,d)$. Our proof is based on the junta method for extremal combinatorics initiated by Dinur and Friedgut and further developed by Ellis, Keller, and the author.

arXiv comment15 pages