Extremal Families for the Erdős--Kleitman Problem: The Missing Constructions

Abstract

For integers $n\ge s\ge 2$, let $e(n,s)$ be 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 closely related to the well-known Erdős matching problem. Frankl and Kupavskii posed a meta-conjecture predicting that the maximum is always attained by a weighted family. Fix $m\ge 3$, write $n=ms+c$ with $0\le c<s$, and set $\ell =s-c$. For $0\le k\le m$, let $a_k=ms-kc-1$. For $A\in \left(\genfrac{}{}{0ex}{}{[n]}{a_k}\right)$, define \[ \mathcal H^k(m,s,\ell;A):= \{F\subseteq[n]: k|F|+|F\cap A|\ge m(k+1)\}. \] This defines a unified class of weighted families with matching number less than $s$. Among these families, ${\mathcal{H}}^0$, ${\mathcal{H}}^1$, and ${\mathcal{H}}^m$ were previously known to be extremal in different ranges of $c$. We show that for $1\le k\le m-1$, all families ${\mathcal{H}}^k$ are uniquely extremal in some ranges of $c$. More precisely, we prove that for every $m\ge 3$ and every $1\le k\le m-1$, there exist constants $\hat{I}\pm =\hat{I}\pm (m,k)>0$, ${\hat{I}}^2={\hat{I}}^2(m,k)>0$ and an integer $s_0=s_0(m,k)$ such that, for all integers $s\ge s_0$ and all integers $c$ with $0\le c<s$, the only extremal families for $e(n,s)$ are the families ${\mathcal{H}}^k(m,s,\ell ;A)$ with $A\in \left(\genfrac{}{}{0ex}{}{[n]}{a_k}\right)$ whenever ${\hat{I}}^2{s}^{(k-1)/k}\le c\le \hat{I}\pm s^{k/(k+1)}$. In particular, this result determines an infinite number of new extremal families for the Erdős--Kleitman problem and verifies the Frankl--Kupavskii meta-conjecture in these ranges. This also provides a quantitative extension of the result of Kupavskii and Sokolov on the extremality of ${\mathcal{H}}^1$.

Topics & keywords