Erdős–Kleitman matching problem — 2026 resolution of e(n,s)

Statement

For a family $\mathcal F$ of sets, the matching number $\nu(\mathcal F)$ is the largest number of pairwise disjoint members; an $s$-matching is $s$ pairwise disjoint sets. For integers $n\ge s\ge 2$ define $$ e(n,s)\;\coloneqq\;\max\{\,|\mathcal F| : \mathcal F\subseteq 2^{[n]},\ \nu(\mathcal F)<s\,\}, $$ the maximum size of a family of subsets of $[n]$ with no $s$ pairwise disjoint members. Determining $e(n,s)$ is the Erdős–Kleitman problem — the *non-uniform* analogue of the ($k$-uniform) Erdős matching conjecture erdos/1020. (Definition verbatim, arXiv:2605.09535 §1; problem "goes back to Erdős", Chi–Wang cite [Er], and Kleitman [Kl68].)

Write $n=ms+c=(m+1)s-\ell$ with integers $c,\ell$, $c+\ell=s$, $0\le c<s$. The value $e(n,s)$ is well understood in the two residue classes $c=0$ and $c=-1$ (Kleitman 1968) but is *sensitive to the position of $n$ between consecutive multiples of $s$*; the substance of the problem is what happens for the intermediate $c$ (equivalently intermediate $\ell$).

Facts

- Origin. Posed by Erdős; the non-uniform quantity is named the Erdős–Kleitman problem (arXiv:2605.09535 §1). Its uniform sibling, the Erdős matching conjecture $f(n;r,k)$, is erdos/1020 on erdosproblems.com — status open (refs [Er65d], [Er71,p.103]; that page itself cites Kleitman [Kl68] for the $n=kr$ case and calls $f(n;r,k)=\max\!\big(\binom{rk-1}{r},\binom{n}{r}-\binom{n-k+1}{r}\big)$ "the Erdős matching conjecture"). The two problems share the *same* two extremal shapes (a "clique/junta" family on a bounded vertex set, $\binom{rk-1}{r}$, and a "cover/star" family of all sets meeting a fixed small set, $\binom{n}{r}-\binom{n-k+1}{r}$). - Kleitman 1968 [Kl68]. Determined $e(ms-1,s)$ and $e(ms,s)$ exactly (the two clean residue classes $c\in\{-1,0\}$). Exact closed-forms not extracted here (unverified in this pass). (arXiv:2605.04379 abstract attributes "$e(sm-1,s)$ and $e(sm,s)$" to Kleitman's 1968 determination; 2605.06389, 2605.09535 concur.) - Frankl–Kupavskii. Determined $e((m+1)s-\ell,s)$ in a bounded small-$\ell$ range — Chi–Wang's Theorem 1.2 records the proven condition as $s\ge \ell m+3\ell+3$, i.e. $\ell\le\frac{s-3}{m+3}$ — and conjectured (Chi–Wang Conjecture 1.1, attributed to Frankl–Kupavskii) that the same closed form $e(n,s)=|P(m,s,\ell)|$ persists for all $1\le\ell\le\lceil s/2\rceil$. The construction $P(m,s,\ell;L)$ is closely connected with the extremal example for the Erdős matching conjecture erdos/1020 ("the connection … can be seen in the following construction", arXiv:2605.06389 intro). (arXiv:2605.06389 abstract + html intro.) - Kupavskii–Sokolov, Nov 2025 (arXiv:2511.21628). Complete solution for $n\le 3s$ (i.e. $m\le 2$): here the average set-size in an $s$-matching is $\le 3$, and a delicate interplay between the *missing* $2$- and $3$-element sets controls the answer; four types of extremal families appear. They note that even a *general conjecture* concerning $e(n,s)$ was missing. (Verbatim, abstract.) - Kupavskii–Sokolov, May 2026 (arXiv:2605.04379). Prove an approximate version of the Frankl–Kupavskii conjecture for $s\ge s_0(m)$. In this program four candidate extremal families are introduced and $e(n,s)=\max$ of their four sizes is conjectured. (Abstract; the "four candidate families / max conjecture" attribution to Kupavskii–Sokolov is stated verbatim in arXiv:2605.09535 abstract.) - Chi–Wang, 7 May 2026 (arXiv:2605.06389) — Frankl–Kupavskii conjecture solved. For every fixed $m\ge3$ and all sufficiently large $s$, the extremal families for $e((m+1)s-\ell,s)$ are exactly $$P(m,s,\ell;L)\coloneqq\{A\subseteq[n]:|A|+|A\cap L|\ge m+1\},\quad |L|=\ell-1,$$ in the range $1\le\ell\le\big(\tfrac{m+1}{2m+1}-o(1)\big)s$. This confirms the Frankl–Kupavskii conjecture for every fixed $m\ge3$ and all large $s$. For $m=3$ they pin down the whole range of $\ell$ for which $P(3,s,\ell;L)$ is extremal, generalizing the Kupavskii–Sokolov $m=3$ theorem. ($P$ is the non-uniform analogue of the "cover/star" EMC extremal family — my reading; the verified claim is the "connection … can be seen in the following construction" statement above.) - Chi–Wang, 10 May 2026 (arXiv:2605.09535) — new range, new extremal family, and a DISPROOF. Complements the small-$\ell$ result above at the *other* end (small $c$, large $\ell$): - New extremal range. For fixed $m\ge3$ there are constants $\beta_m,\delta_m>0$ and $s_0(m)$ such that for $s\ge s_0$, whenever $\beta_m s^{(m-1)/m}\le c\le\delta_m s$ (with $n=ms+c$, $\ell=s-c$), the extremal family for $e(ms+c,s)$ is $$\mathcal P'(m,s,\ell;L')\coloneqq\binom{L'}{m}\cup\binom{[ms+c]}{\ge m+1},\quad |L'|=m\ell-1.$$ - $m=3$ sharp. $\mathcal P'(3,s,\ell;L')$ is the unique extremal family for $t(s)<\ell<s-\big((4/3)^{1/3}+o(1)\big)s^{2/3}$, where $$t(s)=\frac{17-18s+\sqrt{49-852s+1284s^2}}{20}=0.8916\cdots s+O(1).$$ The lower bound $t(s)$ is exact; the constant $(4/3)^{1/3}$ in the upper bound is best possible. - Kupavskii–Sokolov conjecture DISPROVED. The conjecture "$e(n,s)=\max$ of the four candidate sizes" is false: Chi–Wang exhibit a new family $$\mathcal R(m,s,\ell)\coloneqq\{E\in 2^{[n]}:(m-1)|E|+|E\cap[ms-(m-1)c-1]|\ge m^2\}$$ that is strictly larger than each of the four candidates for $\alpha_{\mathrm R}s^{1/2}\le c\le\beta_{\mathrm R}s^{(m-1)/m}$. This new construction also shows the exponent $(m-1)/m$ in the range above is tight. (All verbatim, arXiv:2605.09535 abstract + §1/§5.) - No AI-system involvement is documented in any of the four cited 2025–2026 papers: the abstracts and introductions of arXiv:2605.06389, 2605.09535, 2605.04379, 2511.21628 contain no attribution of the constructions or proofs to a model — this is human extremal-set-theory work. (Verified against those sources; absence-of-attribution, not a claim about the wider process.)

Technique

The shape of the problem. Because $\mathcal F$ is *non-uniform*, a family avoiding an $s$-matching can hoard many *small* sets (which are hard to pack disjointly only in bulk) as well as *large* sets. The right variable is the offset $c=s-\ell$ of $n$ above the multiple $ms$: which construction wins depends on how the "budget" $n$ splits between forcing large sets and stockpiling small ones. The three winning families are all weighted-threshold families of the form "keep $E$ iff $a|E|+|E\cap Z|\ge b$":

- $P(m,s,\ell;L)$: threshold $|A|+|A\cap L|\ge m+1$ on a tiny anchor $L$, $|L|=\ell-1$ — the cover/star regime (small $\ell$). - $\mathcal P'(m,s,\ell;L')$: all sets of size $\ge m+1$, plus all $m$-subsets of a moderate anchor $L'$, $|L'|=m\ell-1$ — the clique-plus-uniform-tail regime (large $\ell$). - $\mathcal R(m,s,\ell)$: threshold $(m-1)|E|+|E\cap Z|\ge m^2$ on $Z=[ms-(m-1)c-1]$ — the intermediate regime the four clean candidates all miss.

Why $\mathcal R$ has no $s$-matching (the reusable move). A one-line weighted double count: if $A_1,\dots,A_s\in\mathcal R$ were disjoint then, summing the defining inequality, $$sm^2\le\sum_{i}\big((m-1)|A_i|+|A_i\cap Z|\big)\le(m-1)n+|Z|=(m-1)(ms+c)+\big(ms-(m-1)c-1\big)=sm^2-1,$$ a contradiction (arXiv:2605.09535, verbatim). The $(m-1)$-weight is tuned so the two linear terms telescope to exactly $sm^2-1$ — the construction *is* this inequality run backwards. This "define the family by the tight case of a weighted-counting / Additive-energy / pigeonhole averaging identity — $\sum_n r_A(n)=|A|^2$ forces large representation values on the dense side bound" is the transferable design principle behind all three families.

Extremality and uniqueness. Upper bounds go via a Stability method — bootstrapping an asymptotic extremal bound into an exact/unique result via 'near-extremal ⇒ structurally close to extremal' argument: show any near-extremal $\mathcal F$ must look like one of the threshold families, then a careful accounting of the *missing* small sets (in §5.2 of arXiv:2605.09535 the "bad" singletons/pairs are split into four classes $\mathcal U_1,\dots,\mathcal U_4$ by their intersection pattern with the vertex cover) forces exact equality only for the named family. The tight residue-class base cases (Kleitman's $c\in\{-1,0\}$) and Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983)-type slack across intermediate $c$ are what make the ranges of the three theorems abut and the extremal thresholds ($t(s)$ exact, $(4/3)^{1/3}$ best possible) sharp rather than merely asymptotic.

What remains open. The three theorems cover small $\ell$ ($c$ large), large $\ell$ ($c$ small down to $\beta_m s^{(m-1)/m}$), and $n\le 3s$ ($m\le2$); the intermediate offset $\alpha_{\mathrm R}s^{1/2}\lesssim c\lesssim\beta_{\mathrm R}s^{(m-1)/m}$ — exactly where $\mathcal R$ beats the old candidates — has no conjectured closed form for $e(n,s)$: the disproof of the Kupavskii–Sokolov conjecture means the extremal family there is not yet identified. A finite-search / SAT/CP-SAT-based finite counterexample search and verification attack on small $(m,s,c)$ to guess the true intermediate extremal family is the natural next experiment.

Related

- erdos/1020 — the uniform Erdős matching conjecture $f(n;r,k)$ (the *numbered* Erdős problem, still open); the Erdős–Kleitman $e(n,s)$ on this page is its non-uniform analogue and its three extremal families are the non-uniform images of #1020's two extremal shapes. The single most important edge: this concept is *not* #1020, but lives right beside it. - Δ-system / sunflower — the core combinatorial object — the extremal-set-theory / intersecting-family technique hub (Deza–Erdős–Frankl "extract-a-Δ-system-then-analyze-the-core"); the Erdős–Kleitman problem sits in the same "how large can a family avoiding a configuration be" landscape. (Whether the 2026 proofs *use* sunflower extraction specifically is unverified; the link is topical.) - Stability method — bootstrapping an asymptotic extremal bound into an exact/unique result via 'near-extremal ⇒ structurally close to extremal' — the from-approximate-to-exact / uniqueness engine used to upgrade the extremal *value* to a unique extremal *family* in arXiv:2605.06389, 2605.09535. - Additive-energy / pigeonhole averaging identity — $\sum_n r_A(n)=|A|^2$ forces large representation values on the dense side — the weighted double-count that both *bounds* the matching number and *defines* the winning family $\mathcal R$ (tight case of the same inequality). - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — the deficit-accounting ("bad singletons/pairs", classes $\mathcal U_1,\dots,\mathcal U_4$) that makes the thresholds $t(s)$ and $(4/3)^{1/3}$ sharp. - SAT/CP-SAT-based finite counterexample search and verification — proposed finite-search route to guess the still-unknown extremal family in the intermediate offset range $s^{1/2}\lesssim c\lesssim s^{(m-1)/m}$ where the Kupavskii–Sokolov four-candidate conjecture was disproved.