pith. machine review for the scientific record. sign in

arxiv: 2605.04379 · v1 · submitted 2026-05-06 · 🧮 math.CO · cs.DM

Recognition: unknown

More on the ErdH os--Kleitman problem on matchings in set families

Andrey Kupavskii, Georgy Sokolov

Pith reviewed 2026-05-08 16:11 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords Erdős-Kleitman problemmatching in set familiesErdős Matching Conjectureextremal set theoryapproximate extremal functionsintersecting families
0
0 comments X

The pith

For large s the maximum family without s disjoint sets is approximately given by the Erdős Matching Conjecture construction.

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

The function e(n,s) measures the largest collection of subsets of an n-element ground set that contains no s pairwise disjoint members. Kleitman solved the problem exactly when n equals sm-1 or sm. Frankl and Kupavskii later solved it for n = s(m+1) minus a small ℓ and conjectured that the same type of extremal example remains optimal all the way up to ℓ = s/2. This paper establishes an approximate version of that conjecture once s is at least some threshold depending only on m.

Core claim

We prove that for every m and all s at least some s0(m), the value e(s(m+1)-ℓ,s) differs from the size of the Erdős Matching Conjecture extremal example by a relative error that tends to zero as s grows, uniformly for ℓ up to s/2.

What carries the argument

The extremal function e(n,s) together with the construction from the Erdős Matching Conjecture that takes all sets meeting a fixed m-element set or all sets of size at least some threshold.

If this is right

  • The extremal size e(s(m+1)-ℓ,s) is determined up to lower-order terms by the Erdős Matching Conjecture example once s exceeds s0(m).
  • The same approximate statement holds uniformly across the full range ℓ ≤ s/2.
  • Any future exact solution for the remaining range of ℓ must therefore be asymptotically consistent with the Erdős Matching Conjecture construction.

Where Pith is reading between the lines

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

  • The result suggests that computational searches for exact extremal families can safely restrict attention to perturbations of the Erdős Matching Conjecture examples when s is large.
  • It raises the question whether the same approximate control extends to other ranges of n and s not covered by the current statement.

Load-bearing premise

The extremal examples for large s stay structurally close to the known constructions of the Erdős Matching Conjecture and the error can be bounded without extra assumptions.

What would settle it

Exhibit, for some fixed m and arbitrarily large s, an ℓ ≤ s/2 and a family of size strictly larger than the Erdős Matching Conjecture construction plus the paper's error term.

read the original abstract

Let $e(n,s)$ denote the maximum size of a family $\mathcal{F}$ of subsets of an $n$-element set that contains no $s$ pairwise disjoint members. In 1968, answering a question of Erd\H{o}s, Kleitman determined $e(sm-1,s)$ and $e(sm,s)$ for all integers $m,s\ge 1$. Half a century later, Frankl and Kupavskii determined $e(s(m+1)-\ell, s)$ for $\ell \leq \frac{s-3}{m+3}$. They showed that the corresponding extremal example is closely connected with the extremal example for the Erd\H{o}s Matching Conjecture, and conjectured that the same remains true for all $\ell \leq s/2$. In this paper, we prove an approximate version of their conjecture for $s\ge s_0(m)$.

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.

Referee Report

2 major / 2 minor

Summary. The manuscript proves an approximate version of the Frankl-Kupavskii conjecture for the Erdős-Kleitman problem: for each fixed m and all s ≥ s0(m), the quantity e(s(m+1)−ℓ,s) is at most the size of the largest extremal example from the Erdős Matching Conjecture plus a relative error term that tends to zero as s→∞.

Significance. If the error control holds uniformly, the result supplies the first asymptotic confirmation of the conjecture in the large-s regime and strengthens the structural link between the Erdős-Kleitman problem and the Erdős Matching Conjecture via stability methods. It extends the exact determinations of Kleitman and of Frankl-Kupavskii for small ℓ, and the use of delta-system and stability arguments to control deviations is a technically substantive contribution.

major comments (2)
  1. [§4] §4 (stability argument): the passage from the exact small-ℓ result to the approximate large-s regime relies on a stability lemma whose error term is shown to be o(1) relative to the main term after fixing m, but the dependence of the implicit constants on m is not tracked explicitly; this leaves open whether the o(1) bound remains valid uniformly for the claimed threshold s0(m).
  2. [Theorem 1.2] Theorem 1.2 and the delta-system application in §3.3: the argument that no other constructions can interfere at scale o(binoms) assumes that near-extremal families are structurally close to one of the two EMC examples, yet the quantitative bound on the deviation is not stated with an explicit m-dependent error that would guarantee the approximation for all ℓ ≤ s/2 once s ≥ s0(m).
minor comments (2)
  1. [Introduction] The definition of e(n,s) in the introduction is clear but would benefit from an explicit reminder that the ground set has size n = s(m+1)−ℓ when stating the main theorem.
  2. A few citations to the original Erdős Matching Conjecture papers could be added for readers unfamiliar with the precise statement of the extremal examples.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the stability and quantitative aspects of the proof. We address the major comments point by point below. We will revise the manuscript to clarify the m-dependence of constants and error terms without altering the core arguments.

read point-by-point responses

  1. Referee: [§4] §4 (stability argument): the passage from the exact small-ℓ result to the approximate large-s regime relies on a stability lemma whose error term is shown to be o(1) relative to the main term after fixing m, but the dependence of the implicit constants on m is not tracked explicitly; this leaves open whether the o(1) bound remains valid uniformly for the claimed threshold s0(m).

    Authors: We agree that the presentation would benefit from greater clarity on this point. Since m is fixed throughout the argument, the stability lemma (inherited from the exact small-ℓ results) and all subsequent o(1) estimates have constants that depend only on m. The threshold s0(m) is then chosen large enough, depending on these fixed constants, to ensure that the relative error tends to zero as s → ∞ and remains below the required threshold for the approximation when s ≥ s0(m). This is the natural uniformity for a statement parameterized by fixed m. We will add a clarifying remark in §4 explicitly noting that all implicit constants are m-dependent and absorbed into the choice of s0(m). revision: partial

  2. Referee: [Theorem 1.2] Theorem 1.2 and the delta-system application in §3.3: the argument that no other constructions can interfere at scale o(binoms) assumes that near-extremal families are structurally close to one of the two EMC examples, yet the quantitative bound on the deviation is not stated with an explicit m-dependent error that would guarantee the approximation for all ℓ ≤ s/2 once s ≥ s0(m).

    Authors: The delta-system application in §3.3 is used on families already known to be structurally close to one of the two Erdős Matching Conjecture extremal examples, with the closeness supplied by the stability result. The resulting deviation bounds are o(1) as s → ∞ for each fixed m, and the parameters in the delta-system lemma are chosen depending only on m (and the fixed range ℓ ≤ s/2). This ensures that for s sufficiently large (i.e., s ≥ s0(m)), no other constructions interfere at the scale needed for the approximate statement. While we did not write out an explicit functional form for the error (which would be possible but cumbersome), the existence of such an m-dependent bound is implicit in the proof. We will insert a short explanatory paragraph in §3.3 making this dependence and the resulting guarantee for ℓ ≤ s/2 explicit. revision: partial

Circularity Check

0 steps flagged

Approximate stability result for large s is independent of self-citation chains or fitted inputs.

full rationale

The paper proves an approximate version of the Frankl-Kupavskii conjecture for s ≥ s0(m) by developing stability and error-control arguments that connect near-extremal families to the Erdős Matching Conjecture constructions. While it cites the authors' prior exact results for small ℓ, those citations supply the base cases rather than forcing the large-s approximation by definition or by renaming fitted quantities. No step reduces a claimed prediction to a parameter fit or to a self-referential uniqueness theorem; the derivation remains self-contained once the exact small-ℓ theorems are granted as external input.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard definitions of set families, matchings, and the Erdős Matching Conjecture framework from prior literature; no new free parameters, axioms beyond standard math, or invented entities are introduced.

axioms (1)
  • standard math Basic properties of intersecting families and the definition of e(n,s) as the extremal function.
    Invoked in the statement of the problem and conjecture.

pith-pipeline@v0.9.0 · 5458 in / 1168 out tokens · 29424 ms · 2026-05-08T16:11:11.686356+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

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

    math.CO 2026-05 unverdicted novelty 8.0

    For fixed m≥3 and large s the extremal families achieving e((m+1)s−ℓ,s) are the constructions P(m,s,ℓ;L) with |L|=ℓ−1, confirming the Frankl–Kupavskii conjecture in that regime.

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

    math.CO 2026-05 unverdicted novelty 8.0

    For fixed m≥3 and large s, the extremal families avoiding s disjoint members in 2^[n] with n=(m+1)s-ℓ are exactly the P(m,s,ℓ;L) families with |L|=ℓ-1 for ℓ up to ((m+1)/(2m+1)-o(1))s, confirming the Frankl-Kupavskii ...

  3. Towards the Erd\H{o}s--Kleitman Problem: from Erd\H{o}s matching conjecture perspective

    math.CO 2026-05 unverdicted novelty 7.0

    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.

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

    math.CO 2026-05 unverdicted novelty 7.0

    For fixed m≥3 and large s, the extremal families achieving e((m+1)s−ℓ,s) are exactly the P(m,s,ℓ;L) families when 1≤ℓ≤((m+1)/(2m+1)−o(1))s, confirming the Frankl-Kupavskii conjecture in this regime.

  5. Towards the Erd\H{o}s--Kleitman Problem: from Erd\H{o}s matching conjecture perspective

    math.CO 2026-05 unverdicted novelty 6.0

    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

15 extracted references · 2 canonical work pages · cited by 2 Pith papers · 1 internal anchor

  1. [1]

    Erd˝ os,A problem on independentr-tuples, Ann

    P. Erd˝ os,A problem on independentr-tuples, Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math.8(1965), 93–95

    1965

  2. [2]

    Erd˝ os, T

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

    1959

  3. [3]

    Erd˝ os, C

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

    1961

  4. [4]

    Frankl,The shifting technique in extremal set theory, in:Surveys in Combinatorics, London Math

    P. Frankl,The shifting technique in extremal set theory, in:Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 81–110

    1987

  5. [5]

    Frankl,Improved bounds for Erd˝ os’ Matching Conjecture, J

    P. Frankl,Improved bounds for Erd˝ os’ Matching Conjecture, J. Combin. Theory Ser. A120(2013), 1068–1072

    2013

  6. [6]

    Frankl,Proof of the Erd˝ os Matching Conjecture in a new range, Israel J

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

    2017

  7. [7]

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

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

    2017

  8. [8]

    Frankl, A

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

    2017

  9. [9]

    Frankl, A

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

    2019

  10. [10]

    Frankl, A

    P. Frankl, A. Kupavskii,Families of sets with no matching of sizes3and 4, Eur. J. Combin.75(2019), 123–135

    2019

  11. [11]

    Frankl, A

    P. Frankl, A. Kupavskii,The Erd˝ os Matching Conjecture and concentra- tion inequalities, J. Combin. Theory Ser. B157(2022), 366–400

    2022

  12. [12]

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

    1968

  13. [13]

    Kolupaev, A

    D. Kolupaev, A. Kupavskii,Erd˝ os Matching Conjecture for almost perfect matchings, Discrete Math.346(2023), Article 113281

    2023

  14. [14]

    Kupavskii and G

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

    work page arXiv

  15. [15]

    Families without $s$-matchings: the other end

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

    work page internal anchor Pith review Pith/arXiv arXiv