A complete solution of the Erdős-Kleitman matching problem for $n\le 3s$

Introduction

Let $[n] := \{1,2,\ldots,n\}$ and, more generally, $[a,b] := \{a,a+1,\ldots,b\}$. For a set $X$ and an integer $k$, let $2^X$, $\binom{X}{k}$ and $\binom{X}{\ge k}$ stand for the power set of $X$, the set of its $k$-element subsets and the set of its subsets with size at least $k$, respectively. Any collection of sets is called a family. A matching is a collection of pairwise disjoint sets. An $s$-matching is a matching of size $s$. Given a family $\mathcal{F}$, its matching number $\nu(\mathcal{F})$ is the size of the largest matching in $\mathcal{F}$.

One of the classical topics in extremal set theory is the study of intersecting families, that is, families with matching number 1. Erdős, Ko and Rado [6] showed that the largest intersecting family $\mathcal{F} \subset2^{[n]}$ has size at most $2^{n-1}$, and that for $n \ge2k$ the largest intersecting family $\mathcal{F} \subset\binom{[n]}{k}$ has size $\binom{n-1}{k-1}$. In the several years that followed, Erdős asked for the size of the largest family avoiding an $s$-matching. Let us introduce the following two quantities.

The uniform case

The value of $e_k(n,s)$ is the subject of the famous Erdős Matching Conjecture. Let us define the families $\mathcal{A}_i^{(k)}(n,s)$:

It is not difficult to see that $\nu(\mathcal{A}_i^{(k)}(n,s-1)) \le s-1$ for any $n,s$.

Conjecture 1 (Erdős Matching Conjecture [4]). For $n \ge sk$

Let us comment on the statement of the conjecture. First, the condition $n \ge sk$ is required in order for $\binom{[n]}{k}$ to contain an $s$-matching. Second, note that the conjecture suggests that only two out of $k+1$ families $\mathcal{A}_i$ could be extremal. This is different from some other similar-looking questions, notably, the Complete $t$-Intersection Theorem for $\binom{[n]}{k}$ [1]. There, all families could be extremal depending on the parameters $n,k,t$.

The conjecture (2) is known to be true for $k=2$ [5], and $k=3$ [22, 10]. In fact, an elegant proof of Frankl of the $k=2$ case of the conjecture, initially proven by Erdős and Gallai, will play an important role in this paper. We will recite it later.

The conjecture was proved for $n \ge n_0(s,k)$ by Erdős [4]. Many researchers worked on extending the range in which the conjecture is valid: [4], [3], [17], [15], [8], [14]. Notably, in the last two papers, it is proved that

for $n \ge(2s+1)k-s$ and for $(n \ge\frac{5}{3}sk, s \ge s_0)$, respectively. In [9] and [20], the authors studied the problem from the other end and showed that $\mathcal{A}_k$ is extremal for $(n \le s(k+1/100k), s \ge ck^3$ with some absolute $c>0)$. We refer the reader to [2, 14] for the connections of the Erdős Matching Conjecture and other questions, such as Dirac thresholds and small deviations in probability theory. In [17], [21], the multi-family variant of the EMC was addressed. In [12], a Hilton–Milner type stability result for the EMC is obtained.

The non-uniform case

The study of $e(n,s)$ was also initiated by Erdős at around the same time. The behavior of $e(n,s)$ heavily depends on $n\pmod{s}$. Answering a question of Erdős, Kleitman proved the following theorem.

Theorem 1 (Kleitman [19]).

The matching example for the first case is the family $\binom{[n]}{\geq m}$ of all subsets of $[n]$ of size at least $m$. It is also not difficult to see that $e(sm,s)=2e(sm-1,s)$. In general, $e(n+1,s)\geq2e(n,s)$ because of the doubling construction. Given a family $\mathcal{F}\subset2^{[n]}$ with $\nu(\mathcal{F})<s$, we may construct the doubling $\mathcal{F}'$ of $\mathcal{F}$ as follows: $\mathcal{F}'=\{F\subset[n+1]:F\cap[n]\in\mathcal{F}\}$. It is easy to see that $\nu(\mathcal{F}')<s$ as well.

In [11], Frankl and the first author put forth the following conjecture.

Definition 1. Let $n=sm+s-\ell$, $0<\ell\leq s$. Set

It is not difficult to check (cf. [11]) that $\nu(\mathcal{P}(s,m,\ell))<s$.

Conjecture 2 ([11]). Suppose that $s\geq2$, $m\geq1$, and $n=sm+s-\ell$ for some integer $0<\ell\leq\left\lceil\frac{s}{2}\right\rceil$. Then

They confirmed the conjecture for a variety of cases:

Theorem 2 ([11, 13]). $e(sm+s-\ell,s)=|\mathcal{P}(s,m,\ell)|$ holds for

(i) $\ell=2$,

(ii) $m=1$,

(iii) $s\geq\ell m+3\ell+3$.

The case of $\ell=2$, $s=3$ was solved much earlier by Quinn [23] in his PhD dissertation. We also note that a sum-type inequality for $s$ families avoiding a matching is much easier to obtain, see [12].

Let us return to the definition of $\mathcal{P}(s,m,\ell)$. The two main uniformities to understand the construction are $m$ and $m+1$. One sees that the family contains all sets of size $m+1$, as well as all sets of size $m$ that intersect $[\ell-1]$, i.e., the family $\mathcal{A}^{(m)}_1(n,\ell-1)$. Thus, in fact, the sets of uniformity $m$ form a family with no matching of size $\ell$. We should note here that the sets in $\mathcal{P}(s,m,\ell)\cap\binom{[n]}{\leq m}$, a bulk of which is $\mathcal{A}^{(m)}_1(n,\ell-1)$, could be replaced by any other family in $\binom{[n]}{\leq m}$ with no matching of size $\ell$. As a result, we would obtain a construction of a family in $2^{[n]}$ with no $s$-matching.

Here, one sees that the problems of determining $e(n,s)$ and $e_k(n,s)$ are, in fact, closely connected. In particular, let us give the reason for the constraint $\ell\le s/2$ in Conjecture 2: in this regime, $n \ge2\ell m$, and the result of Frankl [8] guarantees that the largest family in $\binom{[n]}{m}$ with no matching of size $\ell$ is indeed $\mathcal{A}^{(m)}_1(n,\ell-1)$.

Incidentally, one could also interpret the extremal family for $n=sm=sm+s-s$ in the same way: the extremal example consists of all sets of size at least $m+1$, as well as of the family of sets of size $m$ with no $s$-matching. The construction for the sets of uniformity $m$ is, however, different: it is $\mathcal{A}^{(m)}_k(n,s-1)$. Actually, the situation is even more complicated, as is shown in [11]: already for $n=sm+1$ there is a construction in which some $(m+1)$-element sets are missing and that is bigger than constructions with all $(m+1)$-element sets present. Namely, it is the doubling construction.

Concluding the discussion, the authors of [11] state that it is hard to formulate a general conjecture, and that they had already struggled with the case $n=2s+t$ for some small values of $t$.

Main result

In this paper, we find the value of $e(n,s)$ for all $n,s$, provided $n \le3s$. The easy case $n<2s$ is solved in Theorem 2. The cases $n=2s$ and $n=3s$ are answered in (5). Thus, we are left to deal with the cases $2s<n<3s$. For the rest of the paper, unless otherwise stated, we use notation $n=2s+c=3s-\ell$, where $c,\ell\in[s-1]$, $c+\ell=s$.

In order to state the result, we describe the prospective extremal families. We have already seen the first example.