arxiv: 2605.09535 · v2 · submitted 2026-05-10 · 🧮 math.CO

Recognition: no theorem link

Towards the ErdH{o}s--Kleitman Problem: from ErdH{o}s matching conjecture perspective

Cheng Chi, Yan Wang

Pith reviewed 2026-05-13 07:12 UTC · model grok-4.3

classification 🧮 math.CO MSC 05D05

keywords Erdős-Kleitman problemErdős matching conjectureextremal set theorynon-uniform matchingdisjoint sets

0 comments

The pith

For n=sm+c in the range β_m s^{(m-1)/m} ≤ c ≤ δ_m s the largest family without s disjoint members is exactly the P' construction of all m-subsets from a set of size mℓ-1 union all sets of size at least m+1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the extremal size e(n,s) of a family of subsets of [n] containing no s pairwise disjoint members, focusing on the regime n=sm+c for fixed m≥3. It proves that when c lies between β_m s to the power (m-1)/m and δ_m s for large enough s, the unique maximum is attained by the families P'(m,s,ℓ;L') that consist of every m-subset of some L' with |L'|=mℓ-1 together with every set of size at least m+1. A reader cares because this settles the non-uniform Erdős-Kleitman problem in an intermediate range of parameters that had been open, providing concrete progress on a classic question in extremal set theory.

Core claim

For every fixed m≥3 there exist constants β_m and δ_m such that for all sufficiently large s, whenever n=sm+c satisfies β_m s^{(m-1)/m}≤c≤δ_m s, the only extremal families achieving e(sm+c,s) are the sets P'(m,s,ℓ;L')=binom(L',m)∪binom([sm+c],≥m+1) for |L'|=mℓ-1 with ℓ=s-c. For the special case m=3 the paper also determines the asymptotic range of ℓ in which these families remain optimal.

What carries the argument

The P'(m,s,ℓ;L') construction: the union of all m-subsets of a fixed set L' of size mℓ-1 and all subsets of size at least m+1 in the full ground set of size sm+c; this simultaneously caps the number of small sets that can be chosen while forcing any large sets to overlap heavily enough to prevent s disjoint members.

If this is right

The exact value of e(sm+c,s) equals the size of the largest P' family throughout the given window.
The Erdős-Kleitman problem is completely solved for this intermediate range of c between the small-c and large-c regimes.
For m=3 the precise asymptotic interval of ℓ=s-c in which the P' families are optimal is now known.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same style of mixed construction may remain optimal or become suboptimal outside the window, suggesting a threshold phenomenon at c approximately s^{(m-1)/m}.
The result supplies a concrete lower-bound construction that any future full solution of e(n,s) must match or exceed in this parameter region.
Taking uniform slices of these families may yield new information on the classical uniform Erdős matching conjecture.

Load-bearing premise

The argument requires s to be sufficiently large depending on the fixed m and c to lie inside the window β_m s^{(m-1)/m} to δ_m s.

What would settle it

A concrete counterexample would be any family on an n=sm+c ground set, with c inside the stated window for some large s, whose size exceeds that of every possible P' family while still containing no s pairwise disjoint members.

read the original abstract

For integers $n\ge s\ge2$, let $e(n,s)$ denote the maximum size of a family $\F\subseteq2^{[n]}$ with no $s$ pairwise disjoint members. The problem of determining $e(n,s)$, now called the Erd\H{o}s--Kleitman problem, is the non-uniform analogue of the Erd\H{o}s matching problem. Fix $m\ge3$ and write $n=sm+c$, $\ell=s-c$. We prove that for every fixed $m\ge3$, there exists constants $\beta_m$ and $\delta_m$ such that for sufficiently large $s$, the extremal families for $e(sm+c,s)$ are $P'(m,s,\ell;L')\coloneqq \binom{L'}m\cup\binom{[sm+c]}{\ge m+1}$ for some $L'$ with $|L'|=m\ell-1$ when $\beta_m s^{(m-1)/m}\le c\le \delta_m s$. For $m=3$, we determine the asymptotic range of $\ell$ for which $P'(3,s,\ell;L')$ is extremal.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper identifies the exact extremal families for e(sm+c,s) in a new asymptotic window for fixed m using stability from the matching conjecture.

read the letter

The paper pins down the extremal construction for e(n,s) when n = sm + c in the range β_m s^{(m-1)/m} ≤ c ≤ δ_m s for large s and fixed m ≥ 3. This is the main new piece: an explicit family P' = binom(L', m) union binom([n], ≥ m+1) with |L'| = mℓ - 1 that is optimal in that window. They do this well by reducing via stability to known cases of the Erdős matching conjecture. They show that any other family either has smaller size or contains an s-matching, using shifting and deletion methods. The m=3 case sharpens the asymptotic range for ℓ. The argument handles the lower-order terms for fixed m and large s without internal contradictions. The soft spots are that β_m and δ_m are existential constants, not given numerically, and the result is only for sufficiently large s. Outside the window the same P' may not be best, which the paper does not claim. This is standard for such asymptotic results but means the work is a step rather than a complete resolution. This is for people following the Erdős-Kleitman problem and extremal set theory. It gives a concrete template that can be tested in nearby regimes. The work shows clear thinking and honest engagement with the literature, so it deserves a serious referee even if revisions are needed for explicit constants or broader ranges. I would bring this to the next reading group to go through the stability proof in detail.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for every fixed integer m ≥ 3 there exist constants β_m and δ_m such that, for all sufficiently large s, if n = sm + c satisfies β_m s^{(m-1)/m} ≤ c ≤ δ_m s, then the unique extremal families achieving e(n,s) are the constructions P'(m,s,ℓ;L') = binom(L',m) ∪ binom([n], ≥ m+1) with |L'| = mℓ − 1 (ℓ = s − c). For the special case m = 3 the authors additionally determine the asymptotic range of ℓ in which this construction is optimal.

Significance. If the stability argument holds, the result constitutes a meaningful advance on the Erdős–Kleitman problem by characterizing the extremal families throughout a wide intermediate window of the parameter c. The reduction to known cases of the Erdős matching conjecture for large s, together with explicit control of lower-order terms, is a technical strength. The work supplies a concrete template for analyzing transition regimes and leaves open only the determination of optimal constants and the behavior outside the stated window.

minor comments (2)

The abstract introduces the notation P'(m,s,ℓ;L') without a self-contained description of the construction; a single parenthetical clause would improve immediate readability for readers outside the immediate subfield.
A short paragraph comparing the obtained range of c with the known regimes of the Erdős matching conjecture would help situate the novelty of the stability argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our manuscript, as well as their assessment that the work constitutes a meaningful advance on the Erdős–Kleitman problem. We are pleased with the recommendation for minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation reduces to external Erdős matching results

full rationale

The central claim establishes existence of β_m, δ_m and extremal families P' via stability and shifting arguments that compare sizes against candidates and reduce to known large-s cases of the Erdős matching conjecture. No self-definitional steps, no fitted parameters renamed as predictions, and no load-bearing self-citations; the asymptotic window for c is handled by explicit error terms independent of the target quantity. This is a standard non-circular reduction to prior external results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard binomial identities and the definition of the Erdős-Kleitman function; no new free parameters are fitted to data, no new entities are postulated, and the constants β_m, δ_m are shown to exist rather than numerically fitted.

axioms (1)

standard math The binomial coefficient identities and the definition of e(n,s) as the maximum size of an s-matching-free family.
Invoked throughout the statement of the theorem.

pith-pipeline@v0.9.0 · 5510 in / 1438 out tokens · 59840 ms · 2026-05-13T07:12:12.065085+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 3 internal anchors

[1]

Baranyai, On the factorization of the complete uniform hypergraph,Infinite and Finite Sets, Colloq

Zs. Baranyai, On the factorization of the complete uniform hypergraph,Infinite and Finite Sets, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 91–108

work page 1975
[2]

A solution to Frankl and Kupavskii's conjecture concerning Erd\H{o}s-Kleitman matching problem

C. Chi and Y. Wang, A solution to the Frankl–Kupavskii conjecture on the Erdős–Kleitman matching problem, arXiv:2605.06389, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[3]

Erdős, A problem on independentr-tuples,Ann

P. Erdős, A problem on independentr-tuples,Ann. Univ. Sci. Budapest. Eötvös Sect. Math.8(1965), 93–95

work page 1965
[4]

Erdős and T

P. Erdős and T. Gallai, On maximal paths and circuits of graphs,Acta Math. Acad. Sci. Hungar.10(1959), 337–356

work page 1959
[5]

Erdős, C

P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets,Quart. J. Math. Oxford Ser. (2)12(1961), 313–320. 13

work page 1961
[6]

Frankl, On the maximum number of edges in a hypergraph with given matching number,Discrete Appl

P. Frankl, On the maximum number of edges in a hypergraph with given matching number,Discrete Appl. Math.216(2017), 562–581

work page 2017
[7]

Frankl, Proof of the Erdős Matching Conjecture in a new range,Israel J

P. Frankl, Proof of the Erdős Matching Conjecture in a new range,Israel J. Math.222(2017), no. 1, 421–430

work page 2017
[8]

Frankl and A

P. Frankl and A. Kupavskii, Families with nospairwise disjoint sets,J. Lond. Math. Soc. (2)95(2017), no. 3, 875–894

work page 2017
[9]

Frankl and A

P. Frankl and A. Kupavskii, The Erdős Matching Conjecture and concentration inequalities,J. Combin. Theory Ser. B157(2022), 366–400

work page 2022
[10]

Frankl and A

P. Frankl and A. Kupavskii, Two problems on matchings in set families—in the footsteps of Erdős and Kleitman,J. Combin. Theory Ser. B138(2019), 286–313

work page 2019
[11]

M. Guo, H. Lu and D. Mao, A stability result on matchings in3-uniform hypergraphs,SIAM J. Discrete Math.36(2022), no. 3, 2339–2351

work page 2022
[12]

D. J. Kleitman, Maximal number of subsets of a finite set nokof which are pairwise disjoint,J. Combin. Theory5(1968), 157–163

work page 1968
[13]

Kolupaev and A

D. Kolupaev and A. Kupavskii, Erdős matching conjecture for almost perfect matchings,Discrete Math. 346(2023), no. 4, article no. 113304

work page 2023
[14]

Kupavskii and G

A. Kupavskii and G. Sokolov, A complete solution of the Erdős–Kleitman matching problem forn≤3s, arXiv:2511.21628, 2025

work page arXiv 2025
[15]

Families without $s$-matchings: the other end

A. Kupavskii and G. Sokolov, Families withouts-matchings: the other end, arXiv:2605.00996, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[16]

More on the Erd\H os--Kleitman problem on matchings in set families

A. Kupavskii and G. Sokolov, More on the Erdős–Kleitman problem on matchings in set families, arXiv:2605.04379, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[17]

Łuczak and K

T. Łuczak and K. Mieczkowska, On Erdős’ extremal problem on matchings in hypergraphs,J. Combin. Theory Ser. A124(2014), 178–194. A Some numerical estimates We verify (5.3) and (5.4). For (5.3), direct expansion gives Λ3 −D 1 −h 3(n−1, ℓ−4)−B= 13ℓ2 −46ℓs−11ℓ+ 41s 2 + 17s+ 4 2 ,(A.1) and Λ3 −D 2 −h 3(n−2, ℓ−3)−B= 5ℓ2 −14ℓs+ 5ℓ+ 9s 2 −15s+ 8 2 .(A.2) After s...

work page 2014