{"id":"118f5d5a-d8f9-4147-8266-065d9b03fcd7","arxiv_id":"1908.01435","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every subgraph of a binomial random k-uniform hypergraph with minimum co-degree at least (1/2+o(1))np contains a perfect matching, for p ≥ C log n/n.","lead":"This paper proves an optimal resilience result for random hypergraphs: if every set of (k−1) vertices keeps more than half of its usual number of hyperedges, the hypergraph still contains a perfect matching. The constant 1/2 matches the deterministic Dirac-type bound of Kühn and Osthus, giving the sharp random analogue.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.15's WLOG to an A-side Hall violation is unjustified because the pseudorandom definition is one-sided; the B-side case is not ruled out, leaving Theorem 1.1's proof incomplete.","rationale":"The reader's weakest_assumption correctly identifies Lemma 4.15 as the most load-bearing concern. The central theorem depends on converting a pseudorandom auxiliary graph into a perfect matching, and the proof of that conversion skips the B-side Hall case despite the one-sided nature of Definition 4.8. This is a genuine gap in the written proof, not just a stylistic issue. The gap is fixable: one can invoke the standard one-sided Hall theorem (which only checks subsets of A) and then handle all A-side sets, or prove the symmetric pseudorandom properties for Bπ. The fix requires additional argument, so the paper should not be accepted as fully rigorous without it. The other issue, Lemma 4.6's parameter range, is also real but less central. Overall, the mathematical result appears correct and the proof strategy is sound; the missing details do not undermine the theorem's truth, only its current presentation. For this reason, the reader's CONDITIONAL verdict remains appropriate, and our stress-test does not change it.","tokens_in":10329,"tokens_out":33260,"duration_ms":310907,"concrete_test":"Complete the missing B-side case in Lemma 4.15 by hand: assume Y⊆B with |Y|=y≤m/2 and |N(Y)|=x<y. Show that x≥δ(G)≥(1/2+ε)mp, so y>δ(G)>m/10 for large n. Then take X⊇N(Y) with |X|=y+1. Verify that every vertex of Y has all its neighbors in X, so e(X,Y)≥yδ(G). Apply property 3 with |X|-1=|Y|=y to get e(X,Y)≤(1/2+ε/2)mp(y+1). Check that the inequality y(1/2+ε) > (y+1)(1/2+ε/2) holds for y>1/ε+1, which follows from y>δ(G) and the size of mp. If the contradiction goes through, the WLOG is justified and Lemma 4.15 is correct; if not, the lemma needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The final matching lemma (Lemma 4.15) is the step that turns the auxiliary pseudorandom bipartite graph into a perfect matching in H. Its proof asserts that a failure of Hall's condition can be taken, without loss of generality, to be an A-side violation X⊆A. But the pseudorandom conditions in Definition 4.8 bound edge counts only for pairs with |X|-1=|Y| and are not symmetric: the construction of Bπ in Lemma 4.14 randomizes only π1, so Xπ and Vk play different roles. The cited Theorem 4.5 is two-sided, so a Hall violation might occur on the B-side, and the stated pseudorandom properties do not directly rule this out. For example, if Y⊆B violates |N(Y)|<|Y|, the paper offers no argument. A B-side case can be handled with an extra step (enlarge N(Y) to size |Y|+1 and use the minimum degree and property 3), but that step is absent. Because Lemma 4.15 is load-bearing for the main theorem, the proof as written is incomplete. The gap is patchable, but it is not a mere cosmetic omission.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":10420,"tokens_out":21951,"duration_ms":197843,"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":[{"comment":"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.","section":"Lemma 4.15 (proof)"}],"minor_comments":[{"comment":"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.","section":"Lemma 4.6"},{"comment":"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.","section":"Lemma 4.13"},{"comment":"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.","section":"Lemma 4.7"},{"comment":"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.","section":"Proof of Lemma 4.14, property 2"},{"comment":"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.","section":"Proof of Lemma 4.11"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is well within the scope of the journal and the main result is likely correct, but the proof of Lemma 4.15 must be fixed before publication. The gap is not merely cosmetic: Lemma 4.15 is the bridge from pseudorandom auxiliary graphs to perfect matchings. In my reading, the missing B-side argument is routine but not immediate; I have no other reservations about novelty or correctness."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper proves the sharp local resilience threshold for perfect matchings in H^k_{n,p}: for p ≥ C log n/n, the (k−1)-degree condition (1/2+ε)np guarantees a perfect matching, and (1/2−ε)np does not. That closes a natural line, and the constant 1/2 matches the deterministic Dirac-type bound of Kühn–Osthus, so the theorem is exactly what one would hope for. The tightness construction is a clean parity trick and works as sketched.\n\nThe proof is largely self-contained and sensible: partition into k equal parts, build an auxiliary bipartite graph from random permutations, show it is pseudorandom via McDiarmid/Talagrand concentration, then invoke a Hall-type lemma. The lemmas are standard, there are no fitted parameters, and no circularity. The paper is honest about its dependence on prior work.\n\nThe main soft spot is Lemma 4.15, the final matching lemma. The proof says without loss of generality that a Hall violation is witnessed by an A-side set X. That is not justified: the pseudorandom definition is asymmetric (properties 2 and 3 only bound e(X,Y) for |X|−1=|Y| with X⊆A), so a B-side violation Y⊆B is not automatically ruled out. The stress-test note is correct. The gap is real but patchable—one can likely rule out B-side violations by taking X=N(Y), enlarging it to size |Y|+1, and using minimum degree plus property 3, with a separate case for small |Y|. But that argument is absent. Since Lemma 4.15 is the step that turns pseudorandomness into a perfect matching, the proof as written is incomplete. A referee should flag this.\n\nThere is also a small mismatch: Lemma 4.6 is stated for p=ω(log n/n), but the main theorem needs it at p≥C log n/n. The proof actually works for any sufficiently large constant C, so this is a statement fix, not a substantive issue.\n\nVerdict: the result is important, and the proof strategy is sound. With the B-side case added, this should be a solid accept. I would send it to a serious referee without hesitation. Anyone working on resilience or random hypergraph matchings will want this, and the tightness example is simple enough to reuse.","headline":"Optimal co-degree resilience for random hypergraph matchings, with a patchable gap in the final Hall argument.","tokens_in":11092,"tokens_out":5717,"would_cite":true,"duration_ms":55977,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05C70","05C80","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the sharp threshold for preserving perfect matchings in random hypergraphs is a minimum co-degree of half the expected degree.","keywords":["random hypergraphs","perfect matchings","co-degree resilience","local resilience","pseudorandom bipartite graphs","Hall's theorem","Talagrand inequality"],"falsifier":"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.","tokens_in":9981,"feed_emoji":"🎲","tokens_out":3102,"duration_ms":32201,"temperature":0.7,"pith_summary":"The paper determines the exact resilience of a random k-uniform hypergraph against edge deletions that can only be limited by how many edges share a (k−1)-set. It proves that if every (k−1)-set still lies in at least (1/2+ε)np edges, then the hypergraph contains a perfect matching, provided p is at least a large constant times log n/n. It also shows this constant 1/2 is tight, because slightly below it one can delete edges so that every (k−1)-set still has high co-degree yet no perfect matching exists. A sympathetic reader should care because this settles the natural random analogue of the classical Dirac-type matching problem for uniform hypergraphs.","feed_headline":"Half the expected degree decides matchings in random hypergraphs","feed_subtitle":"A random k-uniform hypergraph keeps a perfect matching as long as every (k−1)-set survives in at least half its expected edges.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the deterministic matching theorem for dense hypergraphs with δ_{k−1} ≥ n/2 plus a small error term, which the random setting is compared against and whose tightness idea is adapted.","marker":"[6]"},{"why":"Establishes the threshold for perfect matchings in random hypergraphs, setting the baseline that p ≥ C log n/n lies well above the matching threshold.","marker":"[3]"},{"why":"Supplies the concentration inequality for functions of independent random permutations that is used to show the auxiliary bipartite graph has high minimum degree.","marker":"[7]"},{"why":"Contains a similar pseudorandom bipartite graph argument that the proof of Lemma 4.15 builds on.","marker":"[9]"},{"why":"Provides the Chernoff bounds used throughout to control degrees in the random hypergraph and edge counts in the pseudorandom auxiliary graph.","marker":"[1]"},{"why":"The classical Dirac theorem for graphs motivates the co-degree condition and supplies the general framework of minimum-degree forcing perfect matchings.","marker":"[2]"},{"why":"Justifies the focus on sufficient conditions by noting that finding perfect matchings in hypergraphs is NP-hard.","marker":"[4]"}],"fun_headline_variants":["Half the expected co-degree secures matchings in random hypergraphs","Random hypergraphs retain matchings at half co-degree threshold","Perfect matchings in random hypergraphs require half expected co-degree","Optimal resilience: matchings need half the expected co-degree","Half co-degree threshold for perfect matchings in random hypergraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Half the expected co-degree secures matchings in random hypergraphs","Random hypergraphs retain matchings at half co-degree threshold","Perfect matchings in random hypergraphs require half expected co-degree","Optimal resilience: matchings need half the expected co-degree","Half co-degree threshold for perfect matchings in random hypergraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000456,"raw_usage":{"total_tokens":2243,"prompt_tokens":849,"completion_tokens":1394,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":465,"completion_tokens_details":{"reasoning_tokens":1308}},"tokens_in":465,"tokens_out":1394,"duration_ms":10843,"temperature":1.0,"reasoning_tokens":1308,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:16:49.907509+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"K¨ uhn and D","cited_arxiv_id":null,"evidence_quote":"Provides the deterministic matching theorem for dense hypergraphs with δ_{k−1} ≥ n/2 plus a small error term, which the random setting is compared against and whose tightness idea is adapted."},{"cited_title":"Johansson, J","cited_arxiv_id":null,"evidence_quote":"Establishes the threshold for perfect matchings in random hypergraphs, setting the baseline that p ≥ C log n/n lies well above the matching threshold."},{"cited_title":"McDiarmid, Concentration for independent permutations , Combinatorics, Probability & Computing 11, no","cited_arxiv_id":null,"evidence_quote":"Supplies the concentration inequality for functions of independent random permutations that is used to show the auxiliary bipartite graph has high minimum degree."},{"cited_title":"Sudakov and V","cited_arxiv_id":null,"evidence_quote":"Contains a similar pseudorandom bipartite graph argument that the proof of Lemma 4.15 builds on."},{"cited_title":"Alon and J","cited_arxiv_id":null,"evidence_quote":"Provides the Chernoff bounds used throughout to control degrees in the random hypergraph and edge counts in the pseudorandom auxiliary graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The classical Dirac theorem for graphs motivates the co-degree condition and supplies the general framework of minimum-degree forcing perfect matchings."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Justifies the focus on sufficient conditions by noting that finding perfect matchings in hypergraphs is NP-hard."}],"review_version":1}