Pith. sign in

REVIEW 3 major objections 3 minor 17 references

Positive codegree thresholds for perfect matchings in hypergraphs

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every $k\ge3$, the exact minimum positive codegree forcing a perfect matching in large $k$-uniform hypergraphs is $\frac{k-1}{k}n-(k-2)$, and the bound is sharp.

desk verdict Likely-true result with a real gap in the counting argument of Corollary 4.4; worth reviewing, but not acceptable as-is. read the letter →

arxiv 2505.17981 v1 pith:WUDLFQNZ submitted 2025-05-23 math.CO

Richard Mycroft , Camila Zárate-Guerén This is my paper · ORCID
classification math.CO MSC 05C6505C7005D40
keywords positivecodegreeperfectmatchingk-uniformhypergraphsextremalthresholdfractionalabsorbingmethodDirac-typeproblemsharpnessconstruction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper settles, for every uniformity $k\ge 3$, the exact minimum positive codegree that forces a $k$-uniform hypergraph on $n$ vertices to contain a perfect matching. The theorem states that if $n$ is sufficiently large and divisible by $k$, and $H$ has minimum positive codegree $\delta^+(H)\ge \frac{k-1}{k}n-(k-2)$ and no isolated vertices, then $H$ has a perfect matching. A construction shows the hypothesis cannot be weakened: for every $n$ divisible by $k$ there is a $k$-graph with $\delta^+(H)=\frac{k-1}{k}n-(k-1)$, no isolated vertices, and no perfect matching. Earlier work had the exact threshold only for $k=3$ and, for $k\ge4$, had bounds tight only up to an additive constant; here the constant is removed for all $k$. The consequence is that a much weaker degree notion still forces the spanning matching once isolated vertices are excluded.

What carries the argument

The argument combines three mechanisms. First, a random selection of small sets that can absorb any leftover $k$-set produces an absorbing set $A$ of size $O(\beta n)$; whenever the rest of the proof leaves at most $\beta^2 n$ uncovered vertices, $A$ together with those vertices admits a perfect matching. Second, in the extremal case a small matching is deleted to cover all atypical vertices, the leftover vertices are partitioned into $k$ equal classes, and a classical $k$-partite hypergraph matching theorem supplies a perfect matching of the remainder. Third, in the non-extremal case linear-programming duality proves the existence of a perfect fractional matching, refines it so every pair of vertices carries small total weight, and a recent approximate matching theorem converts it into an integral matching covering all but $\eta n/k$ vertices. The conversion theorem is the step that lets fractional evidence become a genuine near-perfect matching and is therefore the main load-bearing input of the non-extremal proof.

What would settle it

Compute the minimum positive codegree of the split-graph construction with $|A|=n/k+1$ and edges all $k$-sets with $|e\cap A|\le1$: it equals $\frac{k-1}{k}n-(k-1)$, one below the theorem's threshold, and it has no perfect matching. If any $k$-graph with no isolated vertices, $\delta^+(H)\ge\frac{k-1}{k}n-(k-2)$, and no perfect matching could be found for large $n$, Theorem 1.2 would be false; the sharpness example shows exactly how close one can get without crossing the theorem's line.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: for every $k\ge3$ there is an $n_0$ such that, whenever $k\mid n$ and $n\ge n_0$, every $k$-uniform hypergraph $H$ on $n$ vertices with $\delta^+(H)\ge \frac{k-1}{k}n-(k-2)$ and no isolated vertices contains a perfect matching. The constant is best possible. The sharpness witness is the construction in which the vertex set is split into $A$ of size $n/k+1$ and $B$ of the remaining vertices, with edges exactly the $k$-sets meeting $A$ in at most one vertex; its minimum positive codegree is $\frac{k-1}{k}n-(k-1)$, it has no isolated vertices, yet every matching uses at most one vertex of $A$ per edge and so cannot cover $A$. The proof separates graphs that are close to this construction from graphs that are far from it, and handles the two regimes with different matching machinery.

Load-bearing premise

The non-extremal case rests on a recently stated theorem that any fractional matching with each vertex carrying weight at least $1-\varepsilon$ and each pair of vertices sharing total weight at most $\varepsilon$ can be converted into an ordinary matching covering all but a small fraction of the vertices; if that conversion is wrong at the stated precision, the main theorem does not follow.

Editorial extensions

If this is right

  • For each $k\ge3$, the exact threshold for a large perfect matching is $\delta^+(H)\ge\frac{k-1}{k}n-(k-2)$ under the no-isolated-vertices assumption, and the threshold is sharp.
  • The $k=3$ case and the $k\ge4$ near-results are subsumed, with the additive ambiguity removed in every uniformity.
  • The announced result that the same degree condition forces a tight Hamilton cycle would imply this theorem, since a tight cycle contains a perfect matching; the present proof is a shorter, matching-specific argument.
  • Any hypergraph meeting the threshold is either visibly close to the extremal construction, where a direct $k$-partite argument applies, or admits both an absorbing set and a near-perfect matching, so the two regimes together cover all cases.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, a likely extension is the exact positive codegree threshold for tight Hamilton cycles, since the extremal construction here is exactly the obstruction used for cycle problems; the non-extremal conversion theorem would be the crucial input to upgrade.
  • Beyond the paper, the proof's use of the no-isolated-vertices condition is indirect, so the same argument may adapt to hypergraphs with a bounded number of isolated vertices, with an additive shift in the threshold.
  • Beyond the paper, the additive constant $-(k-2)$ arises from counting extensions of $(k-1)$-sets; computational search for small $k$ could test whether the threshold remains exact with a much smaller $n_0$ than the proof supplies.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper determines, for every k≥3, the exact minimum positive codegree threshold that forces a perfect matching in a large k-uniform hypergraph with no isolated vertices. Theorem 1.2 states that δ^+(H) ≥ (k−1)n/k − (k−2) suffices for all sufficiently large n divisible by k, and the construction of Halfpap and Magnan shows this is best possible. The proof splits into an extremal case handled by deleting a small matching and applying the Daykin–Häggkvist theorem, an absorbing lemma built from many small absorbing sets, and a non-extremal case that passes through perfect fractional matchings with small pair weights and then invokes a Pippenger–Spencer-type theorem.

Significance. If correct, the result is a clean and complete resolution of the positive-codegree threshold problem for perfect matchings, improving on the k=3 result of Halfpap and Magnan and on their bounds for k≥4. The proof is remarkably short for this type of exact threshold and combines classical tools (Daykin–Häggkvist, Farkas's lemma, Pippenger–Spencer) with a carefully tailored absorbing argument. The extremal construction showing sharpness is simple and correct. The main reservation is that the non-extremal case leans on Theorem 4.5, restated from the recent preprint [2] by the first author's group; the present manuscript does not prove that input, so the reader cannot fully verify that step from this paper alone.

major comments (3)
  1. [Corollary 4.4, first case (δ^+ drop)] The inference 'each such edge contains a pair in B, at least one vertex of which must be in S. We conclude that some vertex u∈S is in at least εn pairs in B' is not valid as stated: a single B-pair contained entirely in S can lie in all edges S∪{x} and thus account for Ω(n) deleted edges without making any vertex of S incident to many B-pairs. The gap is repairable, because a set S witnessing the δ^+ drop has deg_{H'}(S)≥1, and if a B-pair were contained in S then every edge containing S would be deleted, forcing deg_{H'}(S)=0. Once that observation is added, every deleted edge containing S must contain a B-pair of the form {s,x} with s∈S and x∉S, and each such pair contributes at most one edge S∪{x}, so the stated bound on some u∈S follows. This missing argument should be supplied, since Corollary 4.4 feeds directly into Lemma 4.1 and hence Theorem 1.2.
  2. [Corollary 4.4, final paragraph] The line '1 = ∑_{e∈E_u(H)} w(e) ≥ M εn' is false: an edge containing u may contain several vertices v with uv∈B, so the sum ∑_{v:uv∈B} w_{uv} can be as large as (k−1)∑_{e∋u}w(e) = k−1, not at most 1. The correct conclusion from u being in at least εn pairs of B is k−1 ≥ M εn, i.e. M ≤ (k−1)/(εn). Since the later application only needs pair weights o(1), this can be repaired by choosing ε smaller (for example replacing ε by ε/(k−1) in the corollary), but the displayed inequality as written is not justified.
  3. [Corollary 4.4, isolated-vertex case] The assertion deg_H(v) ≥ (n/2)^{k−1} is not a consequence of the assumed minimum positive codegree condition. Proposition 1.3(ii) gives deg_H(v) ≥ binom(δ^+(H)+k−2, k−1), which is asymptotically (((k−1)/k)^{k−1}/(k−1)!) n^{k−1}, a positive constant times n^{k−1} but generally smaller than (n/2)^{k−1}. The desired conclusion deg_H(v) ≥ 2ε n^{k−1} still follows for ε sufficiently small, so the error is local, but the displayed inequality should be corrected or replaced by a bound with the correct constant.
minor comments (3)
  1. [Lemma 4.3] The assertion 'from which it follows that y·x_e ≥ y·x_{B_i}' is terse; adding one sentence explaining that the index multiset of e majorizes that of B_i (and likewise for e' and A_i) would improve readability.
  2. [Lemma 2.2] The statement that the number of options for each choice of b_i is '> n/4' is asserted quickly; a short derivation showing δ^+(H)−(n−|B|) > n/4 for the relevant range would be helpful.
  3. [Throughout] There are a few minor typographical issues, including inconsistent spacing in expressions such as 'deg( S)' and the use of 'H' instead of 'Hext' in the sentence describing the extremal construction; these should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central threshold is derived from independent external theorems and internally proved propositions, with self-citations used only as provenance or general tools.

full rationale

The proof of Theorem 1.2 is essentially self-contained: the positive codegree threshold (k-1)/k n - (k-2) enters as a hypothesis, the sharpness construction is taken from Halfpap and Magnan [5], and the main machinery is either classical or proved in the paper. Lemma 2.2 uses the Daykin-Haggkvist theorem for k-partite hypergraphs; Lemma 3.1 proves its absorbing structure from the internally proved Proposition 1.3; the non-extremal case combines a Farkas-lemma argument (Lemma 4.3), a small pair-weight refinement (Corollary 4.4), and Theorem 4.5. The only load-bearing self-citation is Theorem 4.5, restated from [2, Corollary 4.5], a companion preprint including the first author. But that theorem is a general Pippenger-Spencer type conversion from a fractional matching with w_u at least 1-epsilon and small pair weights to an almost-perfect integral matching; its hypotheses do not mention or encode the positive codegree threshold being proved, so it does not smuggle in the conclusion. Proposition 1.3 is proved in full in the present paper, with [12] cited only as provenance for a sharpened version. The skeptical concern about the counting step in Corollary 4.4 is a possible correctness gap, not a circular reduction of the theorem to its inputs: it does not show that any conclusion was assumed or that any parameter was fitted from the target statement. There is no fitted input renamed as a prediction, no uniqueness claim imported from the authors, and no ansatz smuggled via citation. The derivation is therefore non-circular, though it inherits proof-risk from the cited companion result [2].

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The theorem has no fitted parameters: the constants gamma = (2k)^{-2k}, beta, alpha = 1/10, epsilon, and nu are chosen to satisfy the hierarchy 1/n << ... and do not appear in the statement. The proof leans on five stated external results (Farkas, Chernoff, Daykin-Häggkvist, Pippenger-Spencer restatement, and the elementary matching fact). No new entities such as particles, mediators, forces, or dimensions are introduced. The only self-citations are [2] and [12], which supply tools rather than the target threshold, and Proposition 1.3 is proved in the paper.

assumptions (5)
  • standard math Farkas' lemma for solvability of finite systems of linear inequalities (Lemma 4.2)
    Used in Lemma 4.3 to conclude that absence of a perfect fractional matching implies existence of a separating vector y, which then forces extremality.
  • standard math Chernoff-type concentration bound for binomial random variables (Theorem 1.4, from Janson-Luczak-Ruciński)
    Used in Lemma 3.1 to show the random family F has the required size and intersection properties with high probability.
  • domain assumption Daykin-Häggkvist theorem: every k-partite k-graph with vertex classes of size n and every vertex degree at least (k−1)n^{k−1}/k has a perfect matching (Theorem 2.1)
    Used in Lemma 2.2 to find a perfect matching in the k-partite subgraph H* after deleting the small matching M.
  • domain assumption Pippenger-Spencer restatement: a fractional matching with w_u ≥ 1−ε and w_{uv} ≤ ε implies a matching covering (1−η)n/k vertices (Theorem 4.5, quoted from [2, Corollary 4.5])
    Used in Lemma 4.1 to pass from a perfect fractional matching with small pair weights to an almost-perfect integral matching. This is the most external and most recent tool, and it comes from a preprint by the same research group.
  • standard math Standard graph fact: every graph on n vertices contains a matching covering at least min(n, 2δ(G)) vertices
    Used in Lemma 2.2 to find the matching MG of size |Y| in the auxiliary graph G.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Positive codegree thresholds for perfect matchings in hypergraphs." pith.science (2026). https://pith.science/paper/WUDLFQNZ

@misc{pith2026250517981,
  author       = {Pith},
  title        = {Pith review of: Positive codegree thresholds for perfect matchings in hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WUDLFQNZ}},
  note         = {Machine review of arXiv:2505.17981}
}
abstract

We give, for each $k \geq 3$, the precise best possible minimum positive codegree condition for a perfect matching in a large $k$-uniform hypergraph $H$ on $n$ vertices. Specifically we show that, if $n$ is sufficiently large and divisible by $k$, and $H$ has minimum positive codegree $\delta^+(H) \geq \frac{k-1}{k}n - (k-2)$ and no isolated vertices, then $H$ contains a perfect matching. For $k=3$ this was previously established by Halfpap and Magnan, who also gave bounds for $k \geq 4$ which were tight up to an additive constant.

Figures

Figures reproduced from arXiv: 2505.17981 by the authors.

Figure 1
Figure 1. For k = 4 the absorbing sets we form in Claim 3.2 have the form shown. Observe that the set of 12 black vertices absorbs the set of 4 red vertices (the vertices in the top row). 3 Absorbing We next show that a substantially weaker minimum positive codegree condition than that of Theorem 1.2 ensures the existence of a small ‘absorbing’ matching in a k-graph H. Lemma 3.1. Suppose that 1/n ≪ β ≪ α, 1/k, and let H be a … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 16 canonical work pages

  1. [2]

    Bowtell, A

    C. Bowtell, A. Kathapurkar, N. Morrison, and R. Mycroft. Perfect tilings of 3-graphs with the generalised triangle. arXiv:2505.05606, 2025

    arXiv 2025

  2. [1]

    Balogh, N

    J. Balogh, N. Lemons, and C. Palmer. Maximum size intersecting families of bounded minimum positive co-degree. SIAM Journal on Discrete Mathematics , 35(3):1525–1535, 2021. 8

    work page 2021

  3. [3]

    D. E. Daykin and R. H¨ aggkvist. Degrees giving independent edges in a hypergraph.Bulletin of the Australian Mathematical Society , 23:103–109, 1981

    work page 1981

  4. [4]

    J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics , 17:449–467, 1965

    work page 1965

  5. [5]

    Positive co-degree thresholds for spanning structures

    A. Halfpap and V. Magnan. Positive co-degree thresholds for spanning structures. arXiv:2409.09185, 2024

    work page Pith review arXiv 2024

  6. [6]

    P. Hall. On representatives of subsets. Journal of the London Mathematical Society , s1– 10:26–30, 1935

    work page 1935

  7. [7]

    Spanning spheres in Dirac hypergraphs

    F. Illingworth, R. Lang, A. M¨ uyesser, O. Parczyk, and A. Sgueglia. Spanning spheres in Dirac hypergraphs. arXiv:2407.06275, 2024

    work page Pith review arXiv 2024

  8. [8]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski. Random graphs. Wiley-Interscience, New York, 2000

    work page 2000

Show all 17 references
  1. [9]

    R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations , The IBM Research Symposia Series, pages 85–103. Plenum Press, 1972

    1972

  2. [10]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. Matchings in hypergraphs of large minimum degree. Journal of Graph Theory, 51:269–280, 2006

    2006

  3. [11]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. Embedding large subgraphs into dense graphs. In Sophie Huczyn- ska, James D. Mitchell, and Colva M. Roney-Dougal, editors, Surveys in Combinatorics 2009, volume 365 of London Mathematical Society Lecture Note Series , pages 137–168. Cambridge Universit...

    2009

  4. [12]

    Mycroft and C

    R. Mycroft and C. Z´ arate-Guer´ en. Positive codegree thresholds for Hamilton cycles in hypergraphs. arXiv:2505.11400, 2025

    2025 arXiv

  5. [13]

    Pippenger and J

    N. Pippenger and J. Spencer. Asymptotic behavior of the chromatic index for hypergraphs. Journal of Combinatorial Theory, Series A , 51:24–42, 1989

    1989

  6. [14]

    R¨ odl and A

    V. R¨ odl and A. Ruci´ nski. Dirac-type questions for hypergraphs — a survey (or more problems for Endre to solve). In Imre B´ ar´ any, J´ ozsef Solymosi, and G´ abor S´ agi, editors, An Irregular Mind , volume 21 of Bolyai Society Mathematical Studies , pages 561–590. Springer, 2010

    2010

  7. [15]

    R¨ odl, A

    V. R¨ odl, A. Ruci´ nski, and E. Szemer´ edi. Perfect matchings in large uniform hypergraphs with large minimum collective degree. Journal of Combinatorial Theory, Series A, 116:613– 636, 2009

    2009

  8. [16]

    W. T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, 22:107–111, 1947

    1947

  9. [17]

    Y. Zhao. Recent advances on Dirac-type problems for hypergraphs. In Andrew Beveridge, Jerrold R. Griggs, Leslie Hogben, Gregg Musiker, and Prasad Tetali, editors,Recent Trends in Combinatorics , volume 159 of The IMA Volumes in Mathematics and its Applications , pages 145–165....

    2016

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.