REVIEW 1 major objections 5 minor 9 references
Co-degrees resilience for perfect matchings in random hypergraphs
T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper proves that the sharp threshold for preserving perfect matchings in random hypergraphs is a minimum co-degree of half the expected degree.
desk verdict Optimal co-degree resilience for random hypergraph matchings, with a patchable gap in the final Hall argument. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proof converts the hypergraph matching problem into a bipartite matching problem. A random or carefully chosen set of permutations π aligns k−1 of the parts into m tuples X_π, and the auxiliary bipartite graph B_π joins a tuple x to a vertex v in the last part exactly when x ∪ {v} is an edge of the k-partite hypergraph; a perfect matching in B_π yields one in the original hypergraph. The paper then shows that this B_π is (ε,p)-pseudorandom, meaning it has high minimum degree and bounded edge counts between certain pairs of subsets, and invokes a lemma that every such pseudorandom bipartite graph contains a perfect matching. Concentration is supplied by a Talagrand-type inequality for independent random permutations, while Chernoff bounds control degrees and edge counts in the random hypergraph.
What would settle it
Search for a bipartite graph G with equal part sizes that satisfies all three conditions of Definition 4.8 but has no perfect matching; Lemma 4.15 claims no such graph exists, so a single counterexample would break the proof of Theorem 1.1 as written. Alternatively, take a candidate graph satisfying conditions 2 and 3 and check directly whether a Hall-deficient set on the right side, handled by taking X = N(Y), can be ruled out using those conditions.
Extended reading notes
Core claim
The central claim is Theorem 1.1: for every integer k, every ε>0, and a sufficiently large constant C, if p ≥ C log n/n then with high probability the binomial k-uniform hypergraph H^k_{n,p} has the property that every spanning subhypergraph with minimum (k−1)-co-degree at least (1/2+ε)np contains a perfect matching. Theorem 1.2 complements this by showing the same statement is false with (1/2−ε)np, via a parity-based deletion construction: partition the vertices into two sets of roughly equal size, delete all edges meeting one part in an odd number of vertices, and the resulting hypergraph has no perfect matching while every (k−1)-set retains co-degree about (1/2−ε)np. Together the two theorems establish that the asymptotic (k−1)-local resilience of a typical H^k_{n,p} at this edge probability is exactly one half of the expected degree.
Load-bearing premise
The proof relies on a lemma that every (ε,p)-pseudorandom bipartite graph has a perfect matching, and inside that lemma it assumes without proof that any Hall obstruction can be taken with the deficient set on a fixed side, even though the pseudorandom conditions treat the two sides asymmetrically and the other side's case is not spelled out.
Editorial extensions
If this is right
- If the proof is correct, the asymptotic (k−1)-local resilience of H^k_{n,p} at p ≥ C log n/n is exactly (1/2)np: every deletion process that keeps each (k−1)-set in at least half the expected number of edges must leave a perfect matching.
- The tightness construction shows the constant 1/2 cannot be improved, because a simple parity-based deletion keeps all (k−1)-set co-degrees near half the expected degree while destroying every perfect matching.
- The result transfers a deterministic matching theorem for dense hypergraphs to the random setting, with the same leading constant, for the full range of p where every (k−1)-set is likely to be contained in some edge.
- Because the auxiliary graph argument is flexible, the same machinery should apply to other spanning structures in random hypergraphs whenever a pseudorandom bipartite graph can be shown to contain the corresponding configuration.
Reading between the lines
- The paper's 1/2 constant may be a general phenomenon for local resilience of perfect matchings in random hypergraphs, potentially extending to lower-degree conditions δ_ℓ for ℓ < k−1 with a different threshold, but that extension is not proved here and could behave differently.
- The asymmetric definition of (ε,p)-pseudorandomness suggests the proof of the key matching lemma could be symmetrized; a reader could test whether a symmetrized definition with both Hall sides checked explicitly yields a simpler and more robust argument.
- One could test the tightness construction computationally for small k and n to confirm that the parity-deleted hypergraph indeed has the claimed co-degree lower bound and no perfect matching, providing an independent check of Theorem 1.2.
- The paper's restriction to p ≥ C log n/n is natural, but an interesting open direction is whether an analogue holds for lower p where isolated (k−1)-sets already force failures; the current method likely does not reach that regime.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proves a sharp co-degree resilience theorem for perfect matchings in the binomial random k-uniform hypergraph H_{n,p}^k. Theorem 1.1 asserts that for every k ≥ 2, every ε > 0, and p ≥ C_{k,ε} log n / n, with high probability every spanning subhypergraph H ⊆ H_{n,p}^k with minimum (k−1)-degree δ_{k−1}(H) ≥ (1/2+ε)np contains a perfect matching. Theorem 1.2 gives a construction showing that the constant 1/2 is asymptotically tight in this range of p. The proof strategy is to partition the vertices into k equal parts so that every (k−1)-set has roughly equal degree into each part, then to randomize one part to build an auxiliary bipartite graph B_π whose perfect matchings lift to perfect matchings in H. The bulk of the paper establishes that B_π can be chosen to satisfy a one-sided pseudorandomness condition (Lemma 4.14), and that every such pseudorandom bipartite graph has a perfect matching (Lemma 4.15).
Significance. The result, if correct, is an optimal 'local resilience' statement for perfect matchings under the (k−1)-degree condition, extending the deterministic Dirac-type theorem of Kühn–Osthus to the random setting and settling the question for all p ≥ C log n / n. The proof is commendably self-contained: it uses only elementary Chernoff bounds, McDiarmid's concentration inequality for random permutations, and Hall's theorem, with no fitted parameters and no invocation of external matching theorems. The tightness construction is both simple and convincing. The central reduction from hypergraph matchings to bipartite matchings is elegant and the exposition is generally clear. The one substantive issue is the proof of Lemma 4.15, which omits a necessary argument for the B-side Hall case; the gap appears repairable, but as written the main theorem does not follow from the stated proof.
major comments (1)
- [Lemma 4.15 (proof)] The proof begins with the assertion that if G has no perfect matching then, 'without loss of generality', there exists X ⊆ A of size x ≤ m/2 and Y ⊆ B of size x−1 with N_G(X) ⊆ Y. This reduction is not justified. Theorem 4.5 is symmetric, so a Hall violation could instead be on the B-side: some Y ⊆ B with |Y| ≤ m/2 and |N_G(Y)| < |Y|. Definition 4.8 is one-sided: properties 2 and 3 only bound e(X,Y) for pairs with X ⊆ A and |X|−1 = |Y|. A B-side violation does not automatically yield an A-side pair of this form: taking X = N_G(Y) gives |X| < |Y|, but N_G(X) need not be contained in any set of size |X|−1, so the stated contradiction with properties 2 or 3 is not immediate. The proof provides no argument for the WLOG. Because Lemma 4.15 is the load-bearing step that turns the auxiliary pseudorandom graph into a perfect matching in H, the proof of Theorem 1.1 is incomplete as written. The gap appears repairable—one can, for instance, start from a B-side violation and use the minimum-degree condition to contradict property 2 or 3 with X = N_G(Y) and a suitable subset Y' of Y—but the missing argument must be supplied.
minor comments (5)
- [Lemma 4.6] The lemma is stated for p = ω(log n/n), but it is invoked in the proof of Theorem 1.1 for p ≥ C log n/n with C a fixed constant, which is not necessarily ω(log n/n). The proof only requires p ≥ C' log n/n for a sufficiently large C', so the statement should be adjusted accordingly.
- [Lemma 4.13] The lemma is stated for p = C log m/m, but in Lemma 4.14 it is applied with p ≥ C log n/n, which after reparameterization is p ≥ C' log m/m. The proof works for all larger p; the statement should say p ≥ C log m/m.
- [Lemma 4.7] The constant C is declared to depend only on ε, but the proof uses the rank k in the union bound (e^{-ε² d_H(X)/k /3} ≤ n^{-k}); the constant should be C(ε,k) or the lemma should be formulated with k fixed throughout the paper.
- [Proof of Lemma 4.14, property 2] The union bound for property 2 sums over x ≥ mp/2; the case x < mp/2 is not discussed. It is harmless because e(X,Y) ≤ x² < xmp/2 there, but a sentence noting this would remove ambiguity.
- [Proof of Lemma 4.11] The variance computation uses implicitly E[B_iB_j] ≤ d_i(v)d_j(v)/(m(m−1)); this inequality should be stated explicitly, since the sets of extensions of A_i∪{v} and A_j∪{v} in V_1 are not necessarily disjoint.
Circularity Check
No circularity: the proof is a self-contained chain from concentration inequalities and Hall's theorem to the resilience theorem, with no fitted parameter renamed as a prediction.
full rationale
The paper derives Theorem 1.1 from independent intermediate statements: a random hypergraph degree concentration lemma (Lemma 4.6), a partition lemma (Lemma 4.7), construction of an auxiliary bipartite graph B_pi (Definition 4.9), pseudorandomness of B_pi for a suitable pi (Lemma 4.14), and a matching lemma for pseudorandom bipartite graphs (Lemma 4.15). None of these inputs is defined in terms of the target theorem, and no parameter is fitted to the conclusion. The threshold 1/2 is not imported from the theorem; it is used in the minimum co-degree assumption and then appears in the properties of B_pi via Chernoff and McDiarmid-type concentration. The tightness construction in Theorem 1.2 explicitly adapts an idea from Kuhn and Osthus, but it is an independent counterexample construction, not an input to the proof of Theorem 1.1. The only notable issue is a possible gap in Lemma 4.15's 'without loss of generality' reduction to an A-side Hall violation, because the pseudorandomness definition is not symmetric; however, this is an incompleteness in justification, not circularity. It does not make the derivation equivalent to its own assumptions, and it concerns a proof detail rather than a reintroduction of the target result as an input. Accordingly, the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- standard math Chernoff-type tail bounds for binomial and hypergeometric variables (Lemma 4.1, Remark 4.2).
- standard math McDiarmid's concentration inequality for independent permutations (Theorem 4.4).
- standard math Two-sided Hall's theorem (Theorem 4.5).
- standard math Hypergeometric concentration for random balanced partitions (Lemma 4.7 proof).
Cite this review
Pith. "Pith review of Co-degrees resilience for perfect matchings in random hypergraphs." pith.science (2026). https://pith.science/paper/F7OBBB4P
@misc{pith2026190801435,
author = {Pith},
title = {Pith review of: Co-degrees resilience for perfect matchings in random hypergraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/F7OBBB4P}},
note = {Machine review of arXiv:1908.01435}
}
abstract
In this paper we prove an optimal co-degrees resilience property for the binomial $k$-uniform hypergraph model $H_{n,p}^k$ with respect to perfect matchings. That is, for a sufficiently large $n$ which is divisible by $k$, and $p\geq C_k\log_n/n$, we prove that with high probability every subgraph $H\subseteq H^k_{n,p}$ with minimum co-degree (meaning, the number of supersets every set of size $k-1$ is contained in) at least $(1/2+o(1))np$ contains a perfect matching.
Reference graph
Works this paper leans on
-
[1]
N. Alon and J. H. Spencer, The probabilistic method , John Wiley & Sons, (2004)
work page 2004
-
[2]
G. A. Dir´ ac, Some theorems on abstract graphs , Proc. London Math. Soc. 2, (1952): 69–81
work page 1952
-
[3]
A. Johansson, J. Kahn, and V. Vu, Factors in random graphs , Random Structures & Algo- rithms 33, no. 1 (2008): 1–28
work page 2008
-
[4]
R. M. Karp, Reducibility among combinatorial problems , Complexity of Computer Computa- tions, (1972): 85-103. 12
work page 1972
-
[5]
Keevash, Hypergraph matchings and designs , Proc
P. Keevash, Hypergraph matchings and designs , Proc. Int. Cong. of Math 3, (2018): 3099–3122
work page 2018
-
[6]
D. K¨ uhn and D. Osthus, Matchings in hypergraphs of large minimum degree , Inc. J Graph Theory 51, (2006): 269–280
work page 2006
-
[7]
C. McDiarmid, Concentration for independent permutations , Combinatorics, Probability & Computing 11, no. 2 (2002): 163–178
work page 2002
-
[8]
V. R¨ odl and A. Ruci´ nski,Dirac-Type Questions for Hypergraphs - A Survey , Bolyai Society Mathematical Studies 21, (2010): 561–590
work page 2010
Show all 9 references
-
[9]
Sudakov and V
B. Sudakov and V. H. Vu, Local resilience of graphs, Random Structures & Algorithms 33, no. 4 (2008): 409–433. 13
2008
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.