A finite-board reduction for the Erdős Matching Conjecture and the 4-uniform case via exact certificates
Jianfeng Hou, Caiyun Hu, Xizhi Liu · 2026
Read A finite-board reduction for the Erdős Matching Conjecture and the 4-uniform case via exact certificates by Jianfeng Hou, Caiyun Hu, Xizhi Liu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26060.txt.
Introduction
Hou, Hu and Liu prove the matching conjecture for four-uniform hypergraphs at matching number 6004 and above. A matching is a set of disjoint edges, and the conjecture caps edges in hypergraphs lacking a larger one. Their proof cuts the global claim to a lower-uniformity bound plus a fixed finite optimisation. For four-uniform hypergraphs the board has 19 vertices, split into 19-, 15- and 11-vertex layers. The hardest layer falls to exact rational certificates and fixed integer searches.
Catalog record
| CREATOR | Jianfeng Hou, Caiyun Hu, Xizhi Liu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91464 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.26060
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A finite-board reduction for the Erdős Matching Conjecture and the 4-uniform case via exact certificates Jianfeng Hou, Caiyun Hu, Xizhi Liu Abstract We prove the 4-uniform Erdős Matching Conjecture for every matching number s ≥ 6961 s\geq 6961 . The proof has two parts. First, building on ideas from Frankl–Rödl–Ruciński [ 14 ] , we formulate a general finite-board criterion for the r r -uniform conjecture. The criterion has two assumptions: the ( r − 1 ) (r-1) -uniform cover-side bound for links with matching number at most t t holds at every m ≥ n r ( t ) m\geq n_{r}(t) , and a finite optimization problem for mixed-size trace configurations on an ( r 2 + r − 1 ) (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 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. 1 Introduction and statement The Erdős Matching Conjecture is one of the central extremal problems for uniform hypergraphs. It asks for the largest possible size of an r -graph when a matching of prescribed size is forbidden. The conjecture was proposed by Erdős [ 3 ] ; in the special case of matching number one it recovers the Erdős–Ko–Rado theorem [ 5 ] . It is also a basic hypergraph Turán problem, with a matching as the excluded configuration, but the expected extremal answer has two competing models rather than a single Turán-type construction. For an r -uniform hypergraph F , let \nu(F) be its matching number. Define m_{r}(n,s)\coloneqq\max\left\{|F|:F\subseteq\binom{[n]}{r},\ \nu(F)\leq s\right\}. The Erdős Matching Conjecture predicts that, for n\geq r(s+1) , m_{r}(n,s)=M_{r}(n,s)\coloneqq\max\{a_{r}(s),b_{r}(n,s)\}, (1) where a_{r}(s)\coloneqq\binom{rs+r-1}{r},\qquad b_{r}(n,s)\coloneqq\binom{n}{r}-\binom{n-s}{r}. The two examples are the complete r -graph on rs+r-1 vertices and the family of all r -sets meeting a fixed s -set. These examples represent the two regimes of the problem: a dense clique-type construction near the minimum admissible number of vertices, and a cover-type construction when the ambient vertex set is large. Historically, the graph case r=2 follows from the theorem of Erdős and Gallai [ 4 ] . Early large- n results for general uniformity go back to Bollobás, Daykin, and Erdős [ 2 ] , and were subsequently strengthened in several directions, including work of Huang, Loh, and Sudakov [ 16 ] , Frankl, Łuczak, and Mieczkowska [ 13 ] , and Frankl [ 7 , 8 , 9 ] . The two extremal regimes have also been studied separately: stability and cover-side large- n results appear in work of Frankl and Kupavskii [ 10 , 11 ] , while the almost-perfect, clique-side range was advanced by Frankl [ 9 ] and Kolupaev and Kupavskii [ 18 ] . A 2026 preprint of Frankl, Lu, Ma, and Wu [ 12 ] proves stability results toward the 4-uniform case and establishes the conjecture in the range n\geq 5s with n sufficiently large. The present paper gives an independent certificate-based proof in an explicit 4-uniform large- s range: all admissible n\geq 4s+4 once s\geq 6961 , whereas Frankl–Lu–Ma–Wu treat the large- n range n\geq 5s with n sufficiently large. The case r=3 is now known in full by Frankl [ 8 ] . Łuczak and Mieczkowska [ 19 ] proved the all- n result for sufficiently large s , and Frankl, Rödl, and Ruciński [ 14 ] gave a short proof in a large- s range. Related matching and degree versions have also played an important role in the development of the area, for example in [ 1 , 15 , 17 ] . As in much of extremal set theory, shifting is a key structural tool; we use it in the standard compressed-family form described, for instance, in Frankl’s survey [ 6 ] . For fixed r , define the transition value n_{r}(s)\coloneqq\min\left\{n\geq r(s+1):\binom{rs+r-1}{r}\leq\binom{n}{r}-\binom{n-s}{r}\right\}. (2) Thus, within the admissible range n\geq r(s+1) , the clique term is strictly larger for n<n_{r}(s) , while the cover term is at least as large for n\geq n_{r}(s) . The main theorem of this paper is the following. Theorem 1.1 (Main theorem) . For every integer s\geq 6961 and every n\geq 4s+4 , every 4 -graph H\subseteq\binom{[n]}{4} with \nu(H)\leq s satisfies |H|\leq M_{4}(n,s) , where M_{4}(n,s)\coloneqq\max\left\{\binom{4s+3}{4},\binom{n}{4}-\binom{n-s}{4}\right\} . We did not try to optimize the lower bound on s in Theorem 1.1 . The numerical constant 6961 is explicit and is the value delivered by the present finite verification: the local 19-board finite-board input is verified uniformly for all s\geq 3481 at the two critical parameter pairs n\in\{n_{4}(s)-1,n_{4}(s)\} , and the non-ONE deletion chain can reduce the matching parameter by almost a factor of two. Thus the global theorem follows for s\geq 2\cdot 3481-1=6961 . The proof has two layers. The first layer, Section 2 , proves a general finite-board criterion for the r -uniform conjecture. After shifting, saturated maximalization, the critical-value reduction, and the non-ONE deletion chain, the global problem is reduced to two assumptions: (i) the (r-1) -uniform EMC gives the cover-side bound \binom{m}{r-1}-\binom{m-t}{r-1} for every m -vertex link with matching number at most t , for all m\geq n_{r}(t) ; and (ii) a finite optimization problem for mixed-size trace configurations on an (r^{2}+r-1) -vertex board, arising from the two critical parameter pairs n\in\{n_{r}(s)-1,n_{r}(s)\} . For r=4 , the parameter comparison in Proposition 3.2 shows that this link range is already beyond the 3-uniform transition threshold, so the known 3-uniform theorem supplies the required lower-uniformity input. The finite-board input is proved on a 19-vertex local board. The second layer, Sections 3 – 8 , verifies these inputs for r=4 . The 19-board inequality is decomposed into three weighted local inequalities: a leading wide layer, a 15-board layer, and an 11-board layer. The leading layer is further split into a top-star branch and a no-top-star branch. The top-star branch is certified by exact rational Farkas certificates; the no-top-star branch is certified by exhaustive finite searches over up-sets; and the lower layers are certified by residual-cut dual certificates. All computations are presented in a certificate style. A program may be used to discover a certificate, but the proof cites only deterministic verification of the certificate. The Farkas certificates are checked after clearing denominators, in the usual linear-programming duality sense [ 20 ] . The no-top-star branch is reduced to finite branch-and-bound searches over principal up-closures, followed by exact arithmetic and rectangle-extension checks. The 15-board and 11-board layers use nonnegative integer combinations of local matching-obstruction rows that dominate the relevant objective coefficient-wise. The ancillary scripts are described in Section 9 ; the proof-critical success markers and the mathematical assertion certified by each script are stated there. All calculations and certificates are available at EMC_certificate.zip . 2 A finite-board criterion for general r This section is written