A finite-board reduction for the Erd\H{o}s Matching Conjecture and the 4-uniform case via exact certificates

Caiyun Hu; Jianfeng Hou; Xizhi Liu

arxiv: 2605.26060 · v1 · pith:YFRHUR4Q · submitted 2026-05-25 · math.CO

A finite-board reduction for the ErdH{o}s Matching Conjecture and the 4-uniform case via exact certificates

Jianfeng Hou , Caiyun Hu , Xizhi Liu This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-06-29 21:20 UTCgrok-4.3pith:YFRHUR4Q record.json open to challenge →

classification math.CO

keywords Erdős Matching Conjecture4-uniform hypergraphsfinite-board criterionexact certificatesmatching numbertrace configurationsdown-set enumeration

0 comments

The pith

The 4-uniform Erdős Matching Conjecture holds for every matching number s at least 6961.

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

The paper formulates a general finite-board criterion that reduces the r-uniform Erdős Matching Conjecture to a lower-uniformity cover-side bound on links together with a finite optimization problem on an (r squared plus r minus 1)-vertex board. For r equals 4 the board has 19 vertices; the required inequality is verified by decomposing it into three weighted layers and solving the resulting exact optimization and certificate problems via down-set enumerations, Farkas-dual certificates, branch-and-bound, and residual-cut duals. This yields the conjecture for all s at least 6961. A reader would care because the reduction converts an open infinite extremal question into a finite, machine-checkable statement whose assumptions are stated explicitly.

Core claim

We prove the 4-uniform Erdős Matching Conjecture for every matching number s≥6961. The proof has two parts. First, building on ideas from Frankl--Röd l--Ruciński, we formulate a general finite-board criterion for the r-uniform conjecture. The criterion has two assumptions: the (r-1)-uniform cover-side bound for links with matching number at most t holds at every m≥n_r(t), and a finite optimization problem for mixed-size trace configurations on an (r^2+r-1)-vertex board. Together with the corresponding lower-uniformity input, this finite-board optimization implies the Erdős Matching Conjecture with explicit large-matching thresholds. Second, we verify the finite-board assumption for r=4. The

What carries the argument

Finite-board criterion that reduces the r-uniform Erdős Matching Conjecture to the (r-1)-uniform cover-side bound on links and a finite optimization problem for mixed-size trace configurations on the (r^2 + r - 1)-vertex board.

If this is right

The 4-uniform Erdős Matching Conjecture holds for every matching number s at least 6961.
The general criterion supplies explicit thresholds once the two assumptions are verified for a given r.
Verification of the finite optimization on the (r^2 + r - 1)-vertex board for other small r would yield analogous thresholds for those uniformities.

Where Pith is reading between the lines

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

If the finite optimization can be carried out on smaller boards or with tighter parameters, the explicit threshold 6961 could be lowered.
The certificate techniques for down-sets and duals may apply directly to other extremal problems that involve trace configurations or weighted layer inequalities.
Independent proofs of the (r-1)-uniform cover-side bound for small matching numbers would make the reduction available for additional uniformities without new computation.

Load-bearing premise

The (r-1)-uniform cover-side bound for links with matching number at most t holds at every m greater than or equal to n_r(t), together with the correctness of the finite optimization problem for mixed-size trace configurations on the (r^2 + r - 1)-vertex board.

What would settle it

A single 4-uniform hypergraph with matching number s at least 6961 whose number of edges strictly exceeds the maximum given by the Erdős Matching Conjecture construction would falsify the result.

read the original abstract

We prove the 4-uniform Erd\H{o}s Matching Conjecture for every matching number $s\ge 6961$. The proof has two parts. First, building on ideas from Frankl--R\"odl--Ruci\'nski, we formulate a general finite-board criterion for the $r$-uniform conjecture. The criterion has two assumptions: the $(r-1)$-uniform cover-side bound for links with matching number at most $t$ holds at every $m\ge n_r(t)$, and a finite optimization problem for mixed-size trace configurations on an $(r^2+r-1)$-vertex board. Together with the corresponding lower-uniformity input, this finite-board optimization implies the Erd\H{o}s Matching Conjecture with explicit large-matching thresholds. Second, we verify the finite-board assumption for $r=4$. The local board has 19 vertices, and the required inequality is decomposed into three weighted local inequalities: a leading wide layer, a 15-board layer, and an 11-board layer. The verification is reduced to exact finite optimization and certificate-validation problems: Ferrers down-set enumerations for pair and triple traces, rational Farkas-dual certificates for the top-star branch, integer branch-and-bound up-set hitting and pattern searches for the no-top-star branch, and residual-cut dual certificates for the 15-board and 11-board layers.

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

They reduce the 4-uniform EMC to a finite 19-vertex optimization and claim to certify it exactly for s at or above 6961.

read the letter

The paper proves the 4-uniform Erdős Matching Conjecture for every matching number s at least 6961. It does this by first writing down a general finite-board criterion that turns the r-uniform statement into two inputs: an assumed (r-1)-uniform cover bound for large enough ground sets, plus an explicit inequality on mixed trace configurations on an (r² + r - 1)-vertex board. For r=4 the board is 19 vertices; they split the target inequality into three weighted layers (19, 15, and 11 vertices) and certify each layer with Ferrers enumerations, rational Farkas duals, integer branch-and-bound, and residual-cut duals.

What is new is the explicit reduction itself and the fact that they carry the verification through for r=4, giving a concrete threshold. The approach is non-circular because the finite optimization is treated as an independent computational task whose solutions are witnessed by dual certificates and exhaustive search. That is real progress on a long-standing conjecture.

The soft spots are the two standing assumptions. The (r-1)-uniform cover bound is taken as given for all large m; if that bound itself requires a separate argument or fails at some scale, the 6961 threshold does not follow. The second assumption is the correctness of the 19-vertex inequality under the chosen weights and case split. The methods they use are standard and exact, but any missed configuration, inexact weight, or invalid dual would invalidate the implication. The paper supplies the certificates, so the claim is in principle checkable, but the load-bearing step is still the computer-assisted verification.

This is for people who work on extremal set theory and hypergraph Turán-type problems. A reader interested in the EMC or in reduction techniques will find the criterion useful even without auditing every certificate. The work deserves a serious referee because the result is new, the method is reusable, and the evidence is presented in a form that can be examined directly.

Referee Report

2 major / 2 minor

Summary. The manuscript formulates a general finite-board criterion reducing the r-uniform Erdős Matching Conjecture to an assumed (r-1)-uniform cover bound for large m together with a finite optimization inequality on mixed-size trace configurations over an (r²+r-1)-vertex board. For r=4 it verifies the board inequality on a 19-vertex board by decomposing it into three weighted local inequalities (19-, 15-, and 11-vertex layers) whose validity is certified exactly via Ferrers enumerations, rational Farkas duals, integer branch-and-bound up-set searches, and residual-cut duals, thereby proving the 4-uniform conjecture for all matching numbers s≥6961.

Significance. If the certificates are valid, the work supplies an explicit large-s threshold for the 4-uniform case and demonstrates a reusable reduction that converts the conjecture into independently checkable finite optimization problems. The use of exact, machine-verifiable certificates (Farkas duals, branch-and-bound, residual cuts) is a notable strength, providing a rigorous computational template for extremal hypergraph problems that avoids heuristic search.

major comments (2)

[Criterion statement] Criterion statement (abstract and first paragraph of the criterion): the reduction treats the (r-1)-uniform cover-side bound as an external input that must hold for all m≥n_r(t); for r=4 this requires the 3-uniform cover bound, and the manuscript should explicitly record whether this input is already known from the literature or remains conditional, since the implication to the 4-uniform EMC rests on it.
[19-vertex board verification] 19-vertex board verification (second part): the three-layer weighted decomposition is load-bearing; while the paper asserts that the sum of the certified local inequalities yields the target board inequality, the explicit weighting coefficients and the verification that no residual slack permits a counterexample configuration should be stated in a single displayed equation or lemma to allow direct inspection.

minor comments (2)

[Abstract] The derivation of the concrete threshold s≥6961 from the board parameters and n_r(t) is not summarized in the abstract or introduction; adding one sentence explaining the arithmetic would improve readability.
Notation for mixed-size trace configurations (e.g., the distinction between top-star and no-top-star branches) is introduced without a small illustrative example; a one-paragraph example on a toy board would clarify the case split.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive recommendation, and constructive suggestions. We address the two major comments point by point below.

read point-by-point responses

Referee: [Criterion statement] Criterion statement (abstract and first paragraph of the criterion): the reduction treats the (r-1)-uniform cover-side bound as an external input that must hold for all m≥n_r(t); for r=4 this requires the 3-uniform cover bound, and the manuscript should explicitly record whether this input is already known from the literature or remains conditional, since the implication to the 4-uniform EMC rests on it.

Authors: We agree with this observation. The finite-board criterion is explicitly formulated as a reduction that takes the (r-1)-uniform cover bound as an assumption (see the statement in Section 2). For r=4, this means the result for the 4-uniform EMC is conditional on the corresponding 3-uniform cover bound holding for large m. This 3-uniform bound is not known unconditionally from the literature for all parameters (the 3-uniform EMC itself is open), though it holds in certain regimes. We will revise the abstract and the opening paragraph of the criterion section to explicitly note that the implication is conditional on this lower-uniformity input. revision: yes
Referee: [19-vertex board verification] 19-vertex board verification (second part): the three-layer weighted decomposition is load-bearing; while the paper asserts that the sum of the certified local inequalities yields the target board inequality, the explicit weighting coefficients and the verification that no residual slack permits a counterexample configuration should be stated in a single displayed equation or lemma to allow direct inspection.

Authors: We appreciate this suggestion for improving clarity. The three-layer decomposition (19-vertex, 15-vertex, and 11-vertex) with specific weights is used to certify the board inequality, and the certificates ensure no counterexample exists. To make this transparent, we will introduce a new displayed equation or lemma (e.g., Lemma 5.3) that explicitly lists the weighting coefficients and shows that their positive linear combination equals the target inequality with zero residual slack, cross-referencing the individual certificates for each layer. revision: yes

Circularity Check

0 steps flagged

No significant circularity; proof reduces to external assumptions plus independently certified finite computations

full rationale

The derivation states a general finite-board criterion whose two assumptions are (1) the (r-1)-uniform cover bound holding for all sufficiently large m (an external inductive hypothesis) and (2) a concrete inequality on the (r²+r-1)-vertex board. For r=4 the board inequality is verified by explicit enumerations (Ferrers down-sets), rational Farkas certificates, integer branch-and-bound, and residual-cut duals. None of these steps re-uses the target Erdős Matching Conjecture statement, redefines a quantity in terms of itself, or relies on a load-bearing self-citation. The finite verifications are self-contained against external benchmarks (exact certificates and exhaustive search), so the overall argument is non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the validity of the (r-1)-uniform input bounds and on the completeness of the three-layer decomposition of the 19-vertex optimization problem; no new entities are postulated.

axioms (2)

domain assumption The (r-1)-uniform cover-side bound holds for links with matching number ≤t at every m≥n_r(t)
Invoked as the first assumption of the finite-board criterion (abstract).
standard math Standard results on Ferrers down-sets, Farkas duality, and integer branch-and-bound are correct
Used to certify the three weighted local inequalities.

pith-pipeline@v0.9.1-grok · 5791 in / 1482 out tokens · 23807 ms · 2026-06-29T21:20:30.391020+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

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

An Erd\H{o}s Matching Conjecture for Vector Spaces
math.CO 2026-06 unverdicted novelty 7.0

Proves the vector-space Erdős matching conjecture m_q(n,k,s) equals the maximum of two explicit constructions in the cases k=2, n=(s+1)k, and large n, with stability and t-cover-free extensions.

Reference graph

Works this paper leans on

20 extracted references · 1 canonical work pages · cited by 1 Pith paper · 1 internal anchor

[1]

N. Alon, P. Frankl, H. Huang, V. R¨ odl, A. Ruci´ nski, and B. Sudakov. Large matchings in uniform hypergraphs and the conjectures of Erd˝ os and Samuels.J. Combin. Theory Ser. A, 119:1200–1215, 2012

2012
[2]

Bollob´ as, D

B. Bollob´ as, D. E. Daykin, and P. Erd˝ os. Sets of independent edges of a hypergraph.Quart. J. Math. Oxford Ser. (2), 27:25–32, 1976

1976
[3]

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

1965
[4]

Erd˝ os and T

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

1959
[5]

Erd˝ os, C

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

1961
[6]

P. Frankl. The shifting technique in extremal set theory. InSurveys in Combinatorics 1987, volume 123 ofLondon Math. Soc. Lecture Note Ser., pages 81–110. Cambridge Univ. Press, Cambridge, 1987

1987
[7]

P. Frankl. Improved bounds for Erd˝ os’ matching conjecture.J. Combin. Theory Ser. A, 120:1068–1072, 2013

2013
[8]

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

2017
[9]

P. Frankl. Proof of the Erd˝ os matching conjecture in a new range.Israel J. Math., 222:421–430, 2017

2017
[10]

Frankl and A

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

2017
[11]

Frankl and A

P. Frankl and A. Kupavskii. The Erd˝ os matching conjecture and concentration inequalities.J. Combin. Theory Ser. B, 157:366–400, 2022

2022
[12]

Towards the Erd\H{o}s matching conjecture for 4-uniform hypergraphs: stability and applications

P. Frankl, H. Lu, J. Ma, and Y. Wu. Towards the Erd˝ os matching conjecture for 4-uniform hypergraphs: stability and applications, 2026. arXiv:2602.19230

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

Frankl, T

P. Frankl, T. Luczak, and K. Mieczkowska. On matchings in hypergraphs.Electron. J. Combin., 19(2):Paper 42, 2012

2012
[14]

Frankl, V

P. Frankl, V. R¨ odl, and A. Ruci´ nski. A short proof of Erd˝ os’ conjecture for triple systems.Acta Math. Hungar., 151:495–509, 2017

2017
[15]

J. Han. Perfect matchings in hypergraphs and the Erd˝ os matching conjecture.SIAM J. Discrete Math., 30(3):1351–1357, 2016

2016
[16]

Huang, P.-S

H. Huang, P.-S. Loh, and B. Sudakov. The size of a hypergraph and its matching number.Combin. Probab. Comput., 21:442–450, 2012

2012
[17]

Huang and Y

H. Huang and Y. Zhao. Degree versions of the Erd˝ os–Ko–Rado theorem and Erd˝ os hypergraph matching conjecture.J. Combin. Theory Ser. A, 150:233–247, 2017

2017
[18]

Kolupaev and A

D. Kolupaev and A. Kupavskii. Erd˝ os matching conjecture for almost perfect matchings.Discrete Math., 346(4):Paper No. 113304, 2023

2023
[19]

Luczak and K

T. Luczak and K. Mieczkowska. On Erd˝ os’ extremal problem on matchings in hypergraphs.J. Combin. Theory Ser. A, 124:178–194, 2014

2014
[20]

not rectangle

A. Schrijver.Theory of Linear and Integer Programming. John Wiley & Sons, Chichester, 1986. 24 A Machine-checkable certificate specifications This appendix gives the finite specifications used by the proof-critical checkers. The files named below are not merely transcripts: each verifier reconstructs the finite universe and then checks that the listed cer...

1986

[1] [1]

N. Alon, P. Frankl, H. Huang, V. R¨ odl, A. Ruci´ nski, and B. Sudakov. Large matchings in uniform hypergraphs and the conjectures of Erd˝ os and Samuels.J. Combin. Theory Ser. A, 119:1200–1215, 2012

2012

[2] [2]

Bollob´ as, D

B. Bollob´ as, D. E. Daykin, and P. Erd˝ os. Sets of independent edges of a hypergraph.Quart. J. Math. Oxford Ser. (2), 27:25–32, 1976

1976

[3] [3]

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

1965

[4] [4]

Erd˝ os and T

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

1959

[5] [5]

Erd˝ os, C

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

1961

[6] [6]

P. Frankl. The shifting technique in extremal set theory. InSurveys in Combinatorics 1987, volume 123 ofLondon Math. Soc. Lecture Note Ser., pages 81–110. Cambridge Univ. Press, Cambridge, 1987

1987

[7] [7]

P. Frankl. Improved bounds for Erd˝ os’ matching conjecture.J. Combin. Theory Ser. A, 120:1068–1072, 2013

2013

[8] [8]

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

2017

[9] [9]

P. Frankl. Proof of the Erd˝ os matching conjecture in a new range.Israel J. Math., 222:421–430, 2017

2017

[10] [10]

Frankl and A

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

2017

[11] [11]

Frankl and A

P. Frankl and A. Kupavskii. The Erd˝ os matching conjecture and concentration inequalities.J. Combin. Theory Ser. B, 157:366–400, 2022

2022

[12] [12]

Towards the Erd\H{o}s matching conjecture for 4-uniform hypergraphs: stability and applications

P. Frankl, H. Lu, J. Ma, and Y. Wu. Towards the Erd˝ os matching conjecture for 4-uniform hypergraphs: stability and applications, 2026. arXiv:2602.19230

work page internal anchor Pith review Pith/arXiv arXiv 2026

[13] [13]

Frankl, T

P. Frankl, T. Luczak, and K. Mieczkowska. On matchings in hypergraphs.Electron. J. Combin., 19(2):Paper 42, 2012

2012

[14] [14]

Frankl, V

P. Frankl, V. R¨ odl, and A. Ruci´ nski. A short proof of Erd˝ os’ conjecture for triple systems.Acta Math. Hungar., 151:495–509, 2017

2017

[15] [15]

J. Han. Perfect matchings in hypergraphs and the Erd˝ os matching conjecture.SIAM J. Discrete Math., 30(3):1351–1357, 2016

2016

[16] [16]

Huang, P.-S

H. Huang, P.-S. Loh, and B. Sudakov. The size of a hypergraph and its matching number.Combin. Probab. Comput., 21:442–450, 2012

2012

[17] [17]

Huang and Y

H. Huang and Y. Zhao. Degree versions of the Erd˝ os–Ko–Rado theorem and Erd˝ os hypergraph matching conjecture.J. Combin. Theory Ser. A, 150:233–247, 2017

2017

[18] [18]

Kolupaev and A

D. Kolupaev and A. Kupavskii. Erd˝ os matching conjecture for almost perfect matchings.Discrete Math., 346(4):Paper No. 113304, 2023

2023

[19] [19]

Luczak and K

T. Luczak and K. Mieczkowska. On Erd˝ os’ extremal problem on matchings in hypergraphs.J. Combin. Theory Ser. A, 124:178–194, 2014

2014

[20] [20]

not rectangle

A. Schrijver.Theory of Linear and Integer Programming. John Wiley & Sons, Chichester, 1986. 24 A Machine-checkable certificate specifications This appendix gives the finite specifications used by the proof-critical checkers. The files named below are not merely transcripts: each verifier reconstructs the finite universe and then checks that the listed cer...

1986