On the union of intersecting families

Abstract

A family of sets is said to be \emph{intersecting} if any two sets in the family have nonempty intersection. In 1973, Erdős raised the problem of determining the maximum possible size of a union of $r$ different intersecting families of $k$-element subsets of an $n$-element set, for each triple of integers $(n,k,r)$. We make progress on this problem, proving that for any fixed integer $r\ge 2$ and for any $k\le (\frac{1}{2}-o(1))n$, if $X$ is an $n$-element set, and $\mathcal{F}={\mathcal{F}}_1\cup {\mathcal{F}}_2\cup \dots \cup {\mathcal{F}}_r$, where each ${\mathcal{F}}_i$ is an intersecting family of $k$-element subsets of $X$, then $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-r}{k}\right)$, with equality only if $\mathcal{F}=\{S\subset X:|S|=k,S\cap R\ne \varnothing \}$ for some $R\subset X$ with $|R|=r$. This is best possible up to the size of the $o(1)$ term, and improves a 1987 result of Frankl and Füredi, who obtained the same conclusion under the stronger hypothesis $k<(3-\sqrt{5})n/2$, in the case $r=2$. Our proof utilises an isoperimetric, influence-based method recently developed by Keller and the authors.

arXiv comment13 pages. Updated references, expositional changes and minor corrections following the helpful comments of an anonymous referee