Beyond the Erdős Matching Conjecture

Abstract

A family $\mathcal{F}\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ is $U(s,q)$ of for any $F_1,\dots ,F_s\in \mathcal{F}$ we have $|F_1\cup \dots \cup F_s|\le q$. This notion generalizes the property of a family to be $t$-intersecting and to have matching number smaller than $s$. In this paper, we find the maximum $|\mathcal{F}|$ for $\mathcal{F}$ that are $U(s,q)$, provided $n>C(s,q)k$ with moderate $C(s,q)$. In particular, we generalize the result of the first author on the Erdős Matching Conjecture and prove a generalization of the Erdős-Ko-Rado theorem, which states that for $n>s^{2}k$ the largest family $\mathcal{F}\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ with property $U(s,s(k-1)+1)$ is the star and is in particular intersecting. (Conversely, it is easy to see that any intersecting family in $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ is $U(s,s(k-1)+1)$.) We investigate the case $k=3$ more thoroughly, showing that, unlike in the case of the Erdős Matching Conjecture, in general there may be $3$ extremal families.