Intersecting families with bounded intersections

Abstract

Let $\mathcal{F}\subset 2^{[n]}$ be an $s$-uniform family such that every two distinct sets have a nonempty intersection but intersect in at most $k$ elements. By the well-known Ray-Chaudhuri--Wilson theorem, since the intersections can take at most $k$ different values, we have $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{k}\right)$. We give a stronger upper bound under our assumptions above, when $n$ is large enough compared to $s$ (and $k+1<s$): $|\mathcal{F}|\le \frac{\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)}{\left(\genfrac{}{}{0ex}{}{s-1}{k}\right)}$. This is a special case of an old theorem of Deza, Erd\H os and Frankl, but our proof is simpler and gives a better threshold for $n$. Furthermore, we prove a generalization of the Erd\H os--Ko--Rado theorem for non-uniform families. Let $\mathcal{F}\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)\cup \left(\genfrac{}{}{0ex}{}{[n]}{k+1}\right)\cup \cdots \cup \left(\genfrac{}{}{0ex}{}{[n]}{s}\right)$, $3\le k\le s$, be a family such that for every two distinct sets the size of the intersection is between 1 and $k-1$ and $n$ is large enough then $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. \emph{Mathematics Subject Classification (2020):} 05D05 \emph{Keywords: intersecting families, uniform families, Ray-Chaudhuri--Wilson theorem, Erd\H os--Ko--Rado theorem}