New Extremal Ranges and Constructions of the Erdős--Kleitman Problem

Abstract

For integers $n\ge s\ge 2$, let $e(n,s)$ denote the maximum size of a family $\mathcal{F}\subseteq 2^{[n]}$ with no $s$ pairwise disjoint members. The problem of determining $e(n,s)$, now called the Erdős--Kleitman problem, is the non-uniform analogue of the Erdős matching conjecture. We prove that for every fixed $m\ge 3$, there exist constants ${\hat{I}}_m^2$ and $\hat{I}{´}_m$ such that for sufficiently large $s$, the extremal families for $e(ms+c,s)$ are \[ \mathcal P'(m,s,\ell;L'):=\binom{L'}m\cup\binom{[ms+c]}{\ge m+1} \] for some $L^{\prime }$ with $\ell =s-c$ and $|L^{\prime }|=m\ell -1$, when ${\hat{I}}_m^2{s}^{(m-1)/m}\le c\le \hat{I}{´}_{m}s$. This determines the extremal families in an unknown range when $\ell$ is large, complementing our earlier work on the range when $\ell$ is small. Moreover, for $m=3$, we sharpen this to the asymptotically optimal range. Let \[ t(s)=\frac{17-18s+\sqrt{49-852s+1284s^2}}{20}=0.8916\cdots s+O(1) \] We prove that \(\mathcal P'(3,s,\ell;L')\) is the unique extremal family when $t(s)<\ell <s-((4/3{)}^{1/3}+o(1))s^{2/3}$. Note that the lower bound \(t(s)\) of $\ell$ is exact, while the the constant \((4/3)^{1/3}\) in the upper bound of $\ell$ is best possible. Kupavskii and Sokolov introduced four candidate extremal families and conjectured that the value of $e(n,s)$ is the maximum of their sizes. We disprove this conjecture by constructing a new family $\mathcal{R}(m,s,\ell )$ that is larger than each of their four proposed candidates when $\hat{I}{\pm }_{\mathrm{R}}{s}^{1/2}\le c\le {\hat{I}}_{\mathrm{R}}^2{s}^{(m-1)/m}$ for some constants $\hat{I}{\pm }_{\mathrm{R}}$ and ${\hat{I}}_{\mathrm{R}}^2$. This also shows that the exponent $(m-1)/m$ in the first result is tight.