Families of Sets with Intersecting Clusters

Abstract

A family of $k$-subsets $A_1,A_2,...,A_d$ on $[n]=\{1,2,...,n\}$ is called a $(d,c)$-cluster if the union $A_1\cup A_2\cup ...\cup A_d$ contains at most $ck$ elements with $c<d$. Let $\mathcal{F}$ be a family of $k$-subsets of an $n$-element set. We show that for $k\ge 2$ and $n\ge k+2$, if every $(k,2)$-cluster of $\mathcal{F}$ is intersecting, then $\mathcal{F}$ contains no $(k-1)$-dimensional simplices. This leads to an affirmative answer to Mubayi's conjecture for $d=k$ based on Chvátal's simplex theorem. We also show that for any $d$ satisfying $3\le d\le k$ and $n\ge \frac{dk}{d-1}$, if every $(d,\frac{d+1}{2})$-cluster is intersecting, then $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ with equality only when $\mathcal{F}$ is a complete star. This result is an extension of both Frankl's theorem and Mubayi's theorem.

14 pages; Final version, to appear in SIAM J. Discrete Math