{"id":"a57d16a5-44ef-4ede-984c-afb7eafc761f","arxiv_id":"2507.11359","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A polynomial-time algorithm almost surely decides whether a random sparsification of a dense k-graph has a perfect matching, and if one exists there are exponentially many.","lead":"This paper shows that the perfect-matching decision problem for dense hypergraphs stays tractable after edges are randomly thinned, provided the edge retention probability remains above a sharp threshold. The result yields polynomial-time algorithms that almost surely decide existence, plus a dichotomy: such hypergraphs contain either no perfect matching or exponentially many.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.10 applies Theorem 6.1 to constant-size clusters from Lemma 5.1, but Theorem 6.1 only holds for n≥n0 with n0≫C; the key F-factor step in each cluster is unsupported as written.","rationale":"I read the paper as establishing a robust decision algorithm by constructing a spread distribution over perfect matchings or F-factors. The key mechanism is Theorem 1.10, which builds the spread distribution by random clustering and then finds an F-factor inside each cluster. The reader's weakest assumption flagged the reduction through Lemma 5.1 and the dependence on Lemma 3.7, but the more basic obstruction is that the clusters have fixed size C while the structural theorem used to find factors inside them is asymptotic. Since R5 forces C to be a constant, the proof cannot escape by enlarging clusters. This is a load-bearing gap: if a cluster of constant size does not provably contain an F-factor under the inherited conditions, the construction of the random embedding ψ does not produce a valid F-factor, and Proposition 2.5 cannot be applied. I do not claim the theorem is false; I claim the written proof is incomplete at a central point. A concrete finite-version lemma for constant clusters, or an alternative clustering with C(n)→∞ that still gives (C'/n)^s vertex-spread, would resolve the concern. Until then, the paper is unverified rather than conditionally acceptable on typographical grounds.","tokens_in":35178,"tokens_out":11426,"duration_ms":136897,"concrete_test":"Derive the probability in Lemma 5.1(R5) for a cluster size C=C(n): a fixed vertex belongs to a specified cluster with probability about C(n)/n, so R5 requires C(n)=O(1). Then inspect Theorem 6.1's hypothesis 'n≥n0' under the hierarchy 1/n0≪1/C: since n0≫C, no cluster from Lemma 5.1 is large enough. A direct verification: attempt to instantiate Theorem 6.1 with n=C and constants β,μ,γ,c satisfying the hierarchy; show that the 'sufficiently large n' quantifier cannot be met because n0 is chosen after (and much larger than) C. Test whether the authors can instead prove a finite version of Theorem 6.1 for constant-size clusters from the inherited degree, reachability and lattice conditions; if no such finite lemma is supplied, Step 3 of Theorem 1.10 is unsupported.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"The proof of Theorem 1.10 relies on Lemma 5.1 to randomly partition V(H) into clusters with |U_i|=C for i≥2, where C is a fixed constant (hierarchy: 1/n≪⋯≪1/C≪β,μ). In Step 3, after moving at most rq vertices and deleting a constant-size packing M1, the graph H_i has |V(H_i)|≥|U'_i|-O(r^2q), still a constant number of vertices. The proof then invokes Theorem 6.1 to obtain an F-factor in H_i. Theorem 6.1 is asymptotic: it requires n≥n0 vertices, and the hierarchy in Theorem 1.10 fixes n0 with 1/n0≪1/C, i.e., n0≫C. Hence the hypotheses of Theorem 6.1 are not satisfied by the constant-size H_i. This is not a technicality about preserving degree or reachability; it is a size obstruction. Moreover, Lemma 5.1's vertex-spread property (R5) forces C=O(1): P[y_i∈U_{f(i)}]≈C/n must be ≤(C'/n)^s, so clusters cannot grow with n as a way out. Thus the central existence step that produces F-factors inside each cluster—and therefore the spread distribution on F-factors—lacks a proof as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies random p-sparsification of dense hypergraphs in the polynomial-time tractable regime of the perfect matching decision problem. For k-uniform hypergraphs with minimum (k-1)-degree at least n/k + γn, Theorem 1.2 gives a deterministic algorithm that, for p ≥ C log n / n^{k-1}, a.a.s. decides whether H_p contains a perfect matching. Theorem 1.8 provides an analogous robustness result for F-factors in graphs with minimum degree above the critical chromatic threshold. The main technical result, Theorem 1.10, constructs a spread distribution on the family of F-factors under structural assumptions, using a new random clustering lemma (Lemma 5.1), the lattice-based absorption method, and the random redistribution framework of Kelly, Müyesser, and Pokrovskiy. Corollaries 1.11 and 1.12 give a dichotomy: either no perfect matching/F-factor exists, or there are exponentially many.","tokens_in":35443,"tokens_out":17476,"duration_ms":193923,"significance":"If the technical gap identified below is closed, these are significant results. They appear to be the first robust random-sparsification versions of polynomial-time tractable perfect matching decision results in hypergraphs, and the counting corollaries give optimal-order lower bounds on the number of perfect matchings under a much weaker degree condition than previous results. The paper is well structured, with full proofs and explicit algorithms, and the strengthened partition lemma (condition (F3)/(P3)) as well as the lattice-preparation step are genuine new ingredients. The proof strategy is coherent and builds on substantial published structural theorems, and the paper is honest about the limitations of the F-factor algorithmic result.","major_comments":[{"comment":"The clusters produced by Lemma 5.1 have constant size: by (R1), |U_i| = C for i ≥ 2 and |U_1| = O(C^2). In Step 3 the proof applies Theorem 6.1 to H_i = H[U'_i \\ V(M_1)], which has |V(H_i)| ≤ C + O(r^2 q) vertices. Theorem 6.1 requires n ≥ n0, and the hierarchy fixed at the start of the proof of Theorem 1.10 (1/n0 ≪ ... ≪ 1/C) gives n0 ≫ C. Thus the hypotheses of Theorem 6.1 are not satisfied for these constant-size subgraphs. This is not a matter of degree or reachability; it is a size obstruction. Since the F-factors inside the clusters are exactly what defines the embedding ψ and yields the vertex-spread bound, the main construction of Theorem 1.10 is unsupported as written. The authors should either reorder the constants so that C is chosen larger than n0 (which appears compatible with Lemma 5.1) or replace this step with a proof that works at constant size.","section":null},{"comment":"The displayed inequality d_{Gπ}(U'_i) ≥ m' - exp(γ^2 C/50)n is false as written: the exponent has the wrong sign and the wrong parameter. It should read m' - exp(-ε^2 C/50)n, as follows from the negation of (A3). This bound is used to show δ(Gπ) ≥ 3m'/4 and hence to apply Lemma 3.7, so the correction is needed for the proof of the spread distribution on the auxiliary bipartite graph.","section":"§5, Lemma 5.1 proof, lower bound on d_{Gπ}(U'_i)"}],"minor_comments":[{"comment":"In the verification of (R1), the text says |U_i| = |U'_i| + 1 = C+1 for i ≥ 2, but |U'_i| = C-1 for i ≥ 2, so this should be C, matching the statement of (R1).","section":"§5, Lemma 5.1 proof, verification of (R1)"},{"comment":"In the probability estimate for the event E_6, the notation 'C2^{|S|}' is undefined; it presumably means C^{2|S|}. Please clarify.","section":"§5, Lemma 5.1 proof, probability estimate"},{"comment":"The abstract uses the notation PM(k,ℓ,0) while the body mostly uses PM(k,δ); unify the notation for readability.","section":"Abstract and §1.1"}],"recommendation":"major_revision","confidential_remarks":"The main gap is the application of the asymptotic Theorem 6.1 to constant-size clusters in the proof of Theorem 1.10. This appears fixable by reordering the constant hierarchy so that C is chosen larger than n0, since Lemma 5.1 does not seem to require C < n0. If such a fix is possible, the paper would be a solid contribution. I also recommend that the authors carefully check the bound on d_{Gπ}(U'_i) in Lemma 5.1, which contains an obvious sign/parameter error that must be corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick note on arXiv:2507.11359. The headline: the main technical theorem has a load-bearing gap, and as written it does not prove the paper's own headline results. The authors apply Theorem 6.1—an asymptotic statement requiring n≥n0—to clusters of constant size C, where the hierarchy forces n0≫C. Each cluster has size C+O(1), so the hypothesis fails. This is not a matter of tuning constants; it is the step that produces an F-factor in each cluster, and without it the vertex-spread distribution has no base case. I do not see a quick fix in the text. You would need either a finite version of Theorem 6.1 that works for all constant-size inputs with uniform bounds, or a different clustering that produces large clusters while retaining (R5). Neither is present.\n\nTo be fair, the paper has real value. The robust decision algorithm for perfect matchings with codegree δ>1/k and the zero-or-exponentially-many counting dichotomy are new and would be important if they hold. The strengthened partition lemma with (P3)/(F3) and the lattice-preparation step are clever and likely reusable. The survey of prior work is accurate, and the proofs are detailed. But the reader's report is too kind: it flags a typo in Lemma 5.1's proof, while missing the cluster-size obstruction, which is the bigger issue. There are also two minor problems: the abstract cites 'Fu et al.' without a reference, and the bound for d_{Gπ}(U'_i) in Lemma 5.1 mixes up m' and n.\n\nBottom line: the paper deserves serious peer review because the ideas are significant and the relevant literature is handled honestly, but my verdict on the current version would be reject-and-resubmit. The authors need to close the constant-size gap. If they do, this could be a strong paper.","headline":"The paper's central proof has a load-bearing gap: it applies an asymptotic structural theorem to constant-size clusters, and the main results rest on that step.","tokens_in":36022,"tokens_out":3506,"would_cite":false,"duration_ms":44192,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05C70","05D40","68Q25","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"Perfect matchings in dense hypergraphs survive random sparsification","keywords":["perfect matchings","hypergraphs","random sparsification","spread distributions","lattice-based absorption","decision problem","F-factors","probabilistic method"],"falsifier":"Find a $k$-graph $H$ with $\\delta_{k-1}(H)\\ge n/k+\\gamma n$ and a probability $p\\ge C\\log n/n^{k-1}$ for which the algorithm in Theorem 1.2 accepts but $H_p$ has no perfect matching with non-vanishing probability; alternatively, exhibit a balanced bipartite graph on $2n$ vertices with minimum degree at least $3n/4$ whose perfect matchings admit no $(C/n)$-spread distribution, which would invalidate the redistribution step of Lemma 5.1.","tokens_in":34935,"feed_emoji":"🎲","tokens_out":9893,"duration_ms":96020,"temperature":0.7,"pith_summary":"This paper claims that the polynomial-time tractable regime for perfect matchings in dense $k$-uniform hypergraphs is stable under random sparsification. For $k\\ge 3$ and $\\gamma>0$, if $H$ has minimum $(k-1)$-degree at least $n/k+\\gamma n$ and every edge is kept independently with probability $p\\ge C\\log n/n^{k-1}$, the authors give a deterministic algorithm with running time $O(n^{2k^2-2k+1})$ that asymptotically almost surely decides whether the random subhypergraph $H_p$ contains a perfect matching. The same robustness is proved for $F$-factors in graphs meeting the critical-chromatic-number degree threshold, and a counting dichotomy follows: such hypergraphs have either no perfect matching or at least $(\\varepsilon n)^{(k-1)n/k}$ perfect matchings. The significance is that the edge-keeping probability at which the decision problem remains tractable matches the natural threshold for the mere existence of perfect matchings in random subgraphs.","feed_headline":"Dense hypergraph matchings survive random sparsification","feed_subtitle":"A polynomial-time algorithm decides perfect matchings with high probability after p-random edge deletion.","key_machinery":"The carrier of the argument is the spread method combined with lattice-based absorption. The paper builds a probability distribution over the perfect matchings (or $F$-factors) of $H$ whose $q$-spread is at most $C''/n^{1/m_1(F)}$, so that a spread-threshold theorem converts the distribution into an a.a.s. guarantee that the structure survives in $H_p$. To build the spread distribution, a random clustering lemma splits the vertex set into constantly many clusters that inherit the degree, reachability, robust-copy, and lattice properties of $H$; a lattice-preparation step then moves a few vertices (the sets $T_i$ and $L_i$) from neighbouring clusters so that each adjusted cluster satisfies the divisibility condition required by the structural theorem from [19], and finally the cluster-by-cluster packing results are glued into a full factor. A strengthened partition lemma (with the new property that every vertex lies in many $\\mu$-robust copies) is what allows the partial-exposure algorithm to reveal only non-robust edges without destroying the conditions needed for the spread argument.","core_discovery":"On the paper's own terms, the central discovery is that the lattice-based absorption theory that makes perfect matching decidable in dense hypergraphs is robust: it survives random edge deletion. Theorem 1.2 states that any $n$-vertex $k$-graph $H$ with $\\delta_{k-1}(H)\\ge n/k+\\gamma n$ admits a deterministic $O(n^{2k^2-2k+1})$-time algorithm such that, for $p\\ge C\\log n/n^{k-1}$, acceptance of the algorithm implies that $H_p$ contains a perfect matching with probability tending to one, while rejection implies $H_p$ has none. The algorithm works by exposing only non-robust edges, leaving the many $\\mu$-robust edges untouched so that they can be used to complete a matching. The main technical engine, Theorem 1.10, constructs a $(C''/n^{1/m_1(F)})$-spread distribution on the family of $F$-factors of a host hypergraph satisfying mild degree, reachability, and robust-copy conditions; from it the authors derive the $F$-factor robustness theorem for graphs and the enumeration dichotomies. The paper thereby identifies the minimum codegree regime $>n/k$ as one where the decision problem is not only tractable but also resilient to random perturbation.","pith_inferences":["The acceptance probability of the algorithm is tied to whether a constant-sized matching of $\\eta$-robust edges with the right index vector exists in $H$; one could test this numerically, giving an easily checkable heuristic certificate for acceptance or rejection before sampling $H_p$.","The lattice-preparation step that separates the two classes of robust index vectors is likely transferable to other contexts where divisibility barriers interact with random perturbation, such as Hamilton cycles in hypergraphs or existence of designs.","The authors note they cannot upgrade the $F$-factor result to a full decision algorithm because verifying divisibility may reveal too many non-robust copies; a route would be to find a way to check divisibility conditions obliviously to the random subgraph.","Since the proof constructs an explicit spread distribution, the counting dichotomy for $H$ plausibly extends to $H_p$ itself: the random sparsification should either have no perfect matching or have many, with the same exponential lower bound, though this is not stated."],"forward_implications":["If Theorem 1.2 is correct, the perfect-matching decision problem for $k$-graphs with minimum codegree at least $n/k+\\gamma n$ is solvable by a deterministic polynomial-time algorithm with high probability after sparsifying down to $p\\approx \\log n/n^{k-1}$.","The probability threshold is best possible up to a constant: when $p=o(\\log n/n^{k-1})$, even the complete $k$-graph a.a.s. loses all perfect matchings.","Corollary 1.11 gives a sharp dichotomy: such a hypergraph either has no perfect matching or has at least $(\\varepsilon n)^{(k-1)n/k}$ perfect matchings, for a constant $\\varepsilon>0$ depending only on $k$ and $\\gamma$.","For graphs, Theorem 1.8 yields the analogous random-sparsification robustness of $F$-factors under the critical chromatic number degree threshold, with an optimal threshold for strictly 1-balanced $F$.","Corollary 1.12 gives the $F$-factor counting dichotomy: either no $F$-factor or at least $(\\varepsilon n)^{e_F n/(r m_1(F))}$ $F$-factors."],"supporting_citations":[{"why":"Structural theorem giving the necessary and sufficient divisibility condition for F-factors in dense hypergraphs; applied to each adjusted cluster to obtain a perfect F-packing.","marker":"[19]"},{"why":"Decision algorithm and partition lemma for perfect matchings in dense k-graphs, whose partial-exposure idea the paper adapts to reveal only non-robust edges.","marker":"[17]"},{"why":"Lemma 3.7: spread distribution on perfect matchings of balanced bipartite graphs with minimum degree 3m'/4, used to redistribute vertices from bad clusters.","marker":"[37]"},{"why":"Random redistribution method and Proposition 2.5 converting vertex-spread embeddings into q-spread distributions on subgraphs; supplies the vertex-spread framework.","marker":"[28]"},{"why":"Spread-threshold theorem: a uniformly random (K q log ℓ)-element subset of a q-spread hypergraph a.a.s. contains an edge; turns a spread distribution into a.a.s. presence in H_p.","marker":"[11]"},{"why":"Coupling between the binomial random graph and random F-complex model, used to sharpen the p-threshold for F-factors of strictly 1-balanced F.","marker":"[38]"},{"why":"Theorem determining δ(F,1,5v_F^2)=1−1/χ_cr(F), the minimum degree threshold for near-perfect F-packings.","marker":"[42]"},{"why":"Theorem giving δ(k,k−1,k)=1/k, the degree threshold underlying the perfect matching case.","marker":"[16]"}],"fun_headline_variants":["Perfect matchings in dense hypergraphs robust to random sparsification","Deterministic algorithm decides perfect matchings after random edge deletion","Random sparsification preserves dense hypergraph perfect matchings","Dense hypergraph matchings persist through random sparsification"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the structural theorem for perfect packings under minimum degree conditions remains valid after the vertex set is randomly partitioned into constant-sized clusters and a few vertices are relocated to correct divisibility; if the reachability, robustness, or lattice conditions are destroyed by these constant-size adjustments, the whole spread construction collapses.","fun_headline_variants_meta":{"raw":{"variants":["Perfect matchings in dense hypergraphs robust to random sparsification","Deterministic algorithm decides perfect matchings after random edge deletion","Random sparsification preserves dense hypergraph perfect matchings","Dense hypergraph matchings persist through random sparsification"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00114,"raw_usage":{"total_tokens":4866,"prompt_tokens":1216,"completion_tokens":3650,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":832,"completion_tokens_details":{"reasoning_tokens":3579}},"tokens_in":832,"tokens_out":3650,"duration_ms":30102,"temperature":1.0,"reasoning_tokens":3579,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:12:23.051354+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a $k$-graph $H$ with $\\delta_{k-1}(H)\\ge n/k+\\gamma n$ and a probability $p\\ge C\\log n/n^{k-1}$ for which the algorithm in Theorem 1.2 accepts but $H_p$ has no perfect matching with non-vanishing probability; alternatively, exhibit a balanced bipartite graph on $2n$ vertices with minimum degree at least $3n/4$ whose perfect matchings admit no $(C/n)$-spread distribution, which would invalidate the redistribution step of Lemma 5.1.","supporting_citations":[{"cited_title":"Han and A","cited_arxiv_id":null,"evidence_quote":"Structural theorem giving the necessary and sufficient divisibility condition for F-factors in dense hypergraphs; applied to each adjusted cluster to obtain a perfect F-packing."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Decision algorithm and partition lemma for perfect matchings in dense k-graphs, whose partial-exposure idea the paper adapts to reveal only non-robust edges."},{"cited_title":"Kelly, A","cited_arxiv_id":null,"evidence_quote":"Random redistribution method and Proposition 2.5 converting vertex-spread embeddings into q-spread distributions on subgraphs; supplies the vertex-spread framework."},{"cited_title":"Frankston, J","cited_arxiv_id":null,"evidence_quote":"Spread-threshold theorem: a uniformly random (K q log ℓ)-element subset of a q-spread hypergraph a.a.s. contains an edge; turns a spread distribution into a.a.s. presence in H_p."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Coupling between the binomial random graph and random F-complex model, used to sharpen the p-threshold for F-factors of strictly 1-balanced F."},{"cited_title":"Shokoufandeh and Y","cited_arxiv_id":null,"evidence_quote":"Theorem determining δ(F,1,5v_F^2)=1−1/χ_cr(F), the minimum degree threshold for near-perfect F-packings."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Theorem giving δ(k,k−1,k)=1/k, the degree threshold underlying the perfect matching case."}],"review_version":1}