Erdős–Kleitman matching conjecture for set families

Less than 1 year old · traced to

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

Ai(k)(n,s)={F∈([n]k):∣F∩[si−1]∣≥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+s−ℓn=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 s≥2s\ge 2, m≥1m\ge 1, and n=sm+s−ℓn=sm+s-\ell for some integer 0<ℓ≤⌈s/2⌉0<\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, s≥ℓm+3ℓ+3s\geq \ell m+3\ell+3, and m=2m=2, while the general assertion remains open.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.