Recognition: no theorem link
A solution to Frankl and Kupavskii's conjecture concerning ErdH{o}s-Kleitman matching problem
Pith reviewed 2026-05-13 06:35 UTC · model grok-4.3
The pith
For fixed m at least 3 and large s, the largest families without s pairwise disjoint sets on (m+1)s minus ell elements are the P(m,s,ell;L) families with |L| equal to ell minus 1.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove that for every fixed m greater than or equal to 3 and sufficiently large s, the extremal families for e((m+1)s minus ell, s) are P(m,s,ell;L) defined as the collection of all A subset of [n] such that |A| plus |A cap L| is at least m+1, for some L with |L| equal to ell minus 1, when 1 less than or equal to ell less than or equal to ((m+1) over (2m+1) minus o(1))s. In particular this confirms the Frankl-Kupavskii conjecture for every fixed m at least 3 and all sufficiently large s. For m equals 3 we determine the whole range of ell for which P(3,s,ell;L) is extremal.
What carries the argument
The families P(m,s,ell;L) = {A subset [n] : |A| + |A cap L| >= m+1} for a fixed set L of size ell minus 1; these constructions achieve the conjectured maximum size and are shown to be the unique extremal examples in the given parameter regime.
If this is right
- The quantity e((m+1)s minus ell, s) equals the cardinality of P(m,s,ell;L) throughout the stated range of parameters.
- The Frankl-Kupavskii conjecture holds for every fixed m at least 3 and all sufficiently large s when ell is at most the fractional threshold.
- For m equals 3 the families P(3,s,ell;L) remain extremal for the entire interval 1 less than or equal to ell less than or equal to ceil(s over 2).
- The result extends the earlier determination of the extremal families for m equals 3 by Kupavskii and Sokolov to the full range of ell.
Where Pith is reading between the lines
- The fractional threshold (m+1) over (2m+1) may mark the precise point at which a different construction becomes larger than P(m,s,ell;L).
- The same structural description could hold for the uniform version of the problem known as the Erdős matching conjecture.
- Direct verification for moderate values of s could test whether the same families remain extremal before the asymptotic regime begins.
Load-bearing premise
That s is large enough relative to the fixed m so the o(1) term vanishes and no other families can exceed the size of these P families.
What would settle it
An explicit family on [(m+1)s minus ell] elements with no s pairwise disjoint members whose cardinality strictly exceeds the size of P(m,s,ell;L) for some fixed m at least 3, sufficiently large s, and ell at most ((m+1)/(2m+1))s.
read the original abstract
For integers $n\ge s\ge2$, let $e(n,s)$ be the maximum size of a family $\mathcal F\subseteq2^{[n]}$ with no $s$ pairwise disjoint members. The study of determining $e(n,s)$ is closely related to its uniform counterpart, the well-known Erd\H{o}s matching conjecture. Frankl and Kupavskii conjectured an exact formula for $e((m+1)s-\ell,s)$ when $1\le \ell\le \lceil s/2\rceil$. We prove that for every fixed $m\ge3$ and sufficiently large $s$, the extremal families for $e((m+1)s-\ell,s)$ are $P(m,s,\ell;L)\coloneqq\{A\subseteq [n]\colon |A|+|A\cap L|\ge m+1\}$ for some $L$ with $|L|=\ell-1$ when $1\le \ell\le (\frac{m+1}{2m+1}-o(1))s$. In particular, this confirms the Frankl--Kupavskii conjecture for every fixed $m\ge3$ and all sufficiently large $s$. For $m=3$, we determine the whole range of $\ell$ for which $P(3,s,\ell;L)$ is extremal, generalizing a theorem of Kupavskii and Sokolov.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that for every fixed m ≥ 3 and all sufficiently large s, the extremal families achieving e((m+1)s − ℓ, s) are the families P(m,s,ℓ;L) ≔ {A ⊆ [n] : |A| + |A ∩ L| ≥ m+1} for some L with |L| = ℓ − 1, provided 1 ≤ ℓ ≤ ((m+1)/(2m+1) − o(1))s. This confirms the Frankl–Kupavskii conjecture in the stated range. For the special case m = 3 the authors determine the extremal families for the entire range 1 ≤ ℓ ≤ ⌈s/2⌉, generalizing an earlier result of Kupavskii and Sokolov.
Significance. If the proof is correct, the result supplies the first structural confirmation of the Frankl–Kupavskii conjecture for all fixed m ≥ 3 and large s, together with an explicit fractional threshold on ℓ. The explicit description of the extremal families P(m,s,ℓ;L) and the extension to the full range when m = 3 constitute a concrete advance in the Erdős–Kleitman matching problem and its uniform counterparts.
major comments (2)
- [§4, Theorem 4.1] §4, Theorem 4.1: the o(1) term in the upper bound on ℓ is not accompanied by an explicit function of m; without a concrete lower bound on s(m) it is impossible to verify that the stability argument remains valid up to the claimed fractional threshold.
- [§5.2, Lemma 5.3] §5.2, Lemma 5.3: the deletion of the o(s) exceptional sets is used to reduce to the case where the family is contained in P(m,s,ℓ;L); the quantitative bound on the number of deleted sets must be shown to be smaller than the gap between |P| and the next-largest construction, otherwise the extremal claim fails for ℓ near the threshold.
minor comments (2)
- [§2] Notation: the dependence of n on s and ℓ is never stated explicitly; adding n ≥ (m+1)s − ℓ + 1 at the beginning of §2 would remove ambiguity.
- [Figure 1] Figure 1: the diagram illustrating P(3,s,ℓ;L) for ℓ = 2 is helpful but the caption does not indicate the value of s used; a concrete small-s example would improve readability.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments. We respond point by point to the major comments below, indicating where revisions will be made.
read point-by-point responses
-
Referee: [§4, Theorem 4.1] the o(1) term in the upper bound on ℓ is not accompanied by an explicit function of m; without a concrete lower bound on s(m) it is impossible to verify that the stability argument remains valid up to the claimed fractional threshold.
Authors: We agree that an explicit function would improve verifiability. The o(1) arises in the proof of Theorem 4.1 from the stability theorem (Theorem 3.2) and parameter choices that absorb error terms for s sufficiently large depending on the fixed m. Deriving a closed-form expression for s0(m) would require tracking constants through multiple applications of the stability and absorption arguments, yielding an impractically large tower-type bound. We will revise the statement of Theorem 4.1 to read 'for all sufficiently large s depending on m' and add a remark in Section 4 explaining the origin of the o(1) term without computing the explicit threshold, preserving the asymptotic focus of the result. revision: partial
-
Referee: [§5.2, Lemma 5.3] the deletion of the o(s) exceptional sets is used to reduce to the case where the family is contained in P(m,s,ℓ;L); the quantitative bound on the number of deleted sets must be shown to be smaller than the gap between |P| and the next-largest construction, otherwise the extremal claim fails for ℓ near the threshold.
Authors: This observation is correct and requires an explicit check near the threshold. In the proof of Lemma 5.3 the number of deleted exceptional sets is bounded by O_m(s) times a lower-order binomial coefficient. The gap between |P(m,s,ℓ;L)| and the size of the next-largest construction is at least c(m) s times a leading binomial term. We will add a direct comparison in the revised Lemma 5.3 (and the surrounding text in §5.2) showing that, for s large enough depending on m, the number of deleted sets is strictly less than half the gap, ensuring the extremal claim remains valid up to the stated fractional threshold. revision: yes
Circularity Check
Direct structural proof with no circular reductions or self-referential fits
full rationale
The paper establishes the extremal families for e((m+1)s−ℓ,s) via a direct proof for fixed m≥3 and large s, identifying them as P(m,s,ℓ;L) without reducing the claimed size or structure to any fitted parameter, self-defined quantity, or load-bearing self-citation chain. The confirmation of the Frankl–Kupavskii conjecture follows from combinatorial arguments on the range of ℓ, generalizing prior external results (Kupavskii–Sokolov) that are independent of the present derivation. No equation or step equates a prediction to its own input by construction, and the result remains self-contained against the conjecture statement.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption e(n,s) is defined as the maximum size of a family of subsets of [n] containing no s pairwise disjoint members.
Forward citations
Cited by 2 Pith papers
-
Towards the Erd\H{o}s--Kleitman Problem: from Erd\H{o}s matching conjecture perspective
For fixed m≥3 and c in the range β_m s^{(m-1)/m} to δ_m s, the extremal families avoiding s disjoint sets are the m-subsets of an (mℓ-1)-set union all sets of size at least m+1.
-
Towards the Erd\H{o}s--Kleitman Problem: from Erd\H{o}s matching conjecture perspective
For fixed m≥3 and sufficiently large s with β_m s^{(m-1)/m} ≤ c ≤ δ_m s, the extremal families achieving e(sm+c,s) are the P'(m,s,ℓ;L') constructions with |L'|=mℓ-1.
Reference graph
Works this paper leans on
-
[1]
Baranyai, On the factorization of the complete uniform hypergraph, inInfinite and Finite Sets, Vol
Zs. Baranyai, On the factorization of the complete uniform hypergraph, inInfinite and Finite Sets, Vol. I, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 91–108
work page 1975
-
[2]
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
-
[3]
P. Erdős and T. Gallai, On maximal paths and circuits of graphs,Acta Math. Acad. Sci. Hungar.10(1959), 337–356. 20
work page 1959
- [4]
-
[5]
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
-
[6]
P. Frankl and A. Kupavskii, Families with nospairwise disjoint sets,J. Lond. Math. Soc. (2)95(2017), no. 3, 875–894
work page 2017
-
[7]
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
-
[8]
P. Frankl and A. Kupavskii, The Erdős Matching Conjecture and concentration inequalities,J. Combin. Theory Ser. B157(2022), 366–400
work page 2022
-
[9]
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
-
[10]
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
-
[11]
A. Kupavskii and G. Sokolov, A complete solution of the Erdős–Kleitman matching problem forn≤3s, arXiv:2511.21628, 2025
-
[12]
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
-
[13]
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
-
[14]
T. Łuczak and K. Mieczkowska, On Erdős’ extremal problem on matchings in hypergraphs,J. Combin. Theory Ser. A124(2014), 178–194. A Numerical estimates in the proof of Theorem 1.4 Lemma A.1.Assume(5.1). Letj∈ {1,2}, put p=ℓ+j−4, N=n−j= 4s−p−4. Then, for all sufficiently larges,N≥3p−1and N 3 − N−p+ 1 3 > 3p−1 3 . Proof. We haveN−3p+ 1 = 4(s−ℓ) + 13−4j >0for...
work page 2014
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.