On the $d$-cluster generalization of Erdős-Ko-Rado

Abstract

If $2\le d\le k$ and $n\ge dk/(d-1)$, a $d$-cluster is defined to be a collection of $d$ elements of $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ with empty intersection and union of size no more than $2k$. Mubayi conjectured that the largest size of a $d$-cluster-free family $\mathcal{F}\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ is $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$, with equality holding only for a maximum-sized star. Here, we resolve Mubayi's conjecture and prove a slightly stronger result, thus completing a new generalization of the Erdős-Ko-Rado Theorem.

Second part removed, important references added, proof simplified