Erdős–Kleitman matching conjecture for set families

From papers

Let e(n,s)e(n,s) denote the maximum size of a family F2[n]\mathcal{F}\subset 2^{[n]} with matching number ν(F)<s\nu(\mathcal{F})<s. For 1ik1\leq i\leq k, let

Ai(k)(n,s)={F([n]k):F[si1]i}.\mathcal{A}_i^{(k)}(n,s)=\Bigl\{F\in {[n]\choose k}:|F\cap [si-1]|\ge i\Bigr\}.

Let P(m,s,)\mathcal{P}(m,s,\ell) be the family defined for n=sm+sn=sm+s-\ell by

P(m,s,)={P[n]:P+P[1]m+1}.\mathcal{P}(m,s,\ell)=\bigl\{P\subset [n]: |P|+|P\cap [\ell-1]|\ge m+1\bigr\}.

Erdős–Kleitman matching conjecture. Suppose that s2s\ge 2, m1m\ge 1, and n=sm+sn=sm+s-\ell for some integer 0<s/20<\ell\leq\lceil s/2\rceil. Then

e(sm+s,s)=P(m,s,).e(sm+s-\ell,s)=|\mathcal{P}(m,s,\ell)|.

The conjecture concerns the extremal size of set families avoiding an ss-matching. It is known in several cases, including =2\ell=2, m=1m=1, sm+3+3s\geq \ell m+3\ell+3, and m=2m=2, while the general assertion remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Andrey Kupavskii and Georgy Sokolov, “More on the Erdős–Kleitman problem on matchings in set families”, arXiv:2605.04379 (2026).

Solutions 0

No solutions have been posted yet.