{"id":"3dcaa4ce-fc5d-4e8e-9ab2-59c6a859e8df","arxiv_id":"2501.19081","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every n >= k >= 2, the matching polynomial of an n-vertex k-uniform hypergraph is uniquely determined by the multiset of induced subgraphs on floor((k-1)/k n)+1 vertices.","lead":"This paper proves that the matching polynomial of any k-uniform hypergraph is determined by the collection of its induced subgraphs on about (k-1)/k of the vertices, a hypergraph analogue of Godsil's 1981 result for graphs. The result also implies that the number of F-tilings of a graph can be reconstructed from a similar deck, and the authors show the vertex fraction is best possible in infinitely many cases.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 1.4 is incomplete: d_H'(v,ℓ,m) depends on a vertex ordering, and the unlabeled deck does not supply orderings or identify v; the leap to 'from C(H,n')' is unjustified.","rationale":"The reader's weakest-assumption analysis identified exactly the gap I find most load-bearing: the transition from the double-counting identity to reconstruction from the unlabeled deck is not established. The proof defines d_{H'}(v,ℓ,m) using a vertex ordering, yet C(H,n') is a multiset of unlabeled subhypergraphs. Additionally, the per-vertex sum over H' containing v is not directly recoverable from the deck; one must either identify v in each unlabeled H' or, more naturally, sum the identity over all v to obtain deck-computable quantities. Neither justification appears in the manuscript. I do not see evidence that the main theorem is false; in fact, closed walks in the walk-tree digraph of a k-tree are likely independent of the chosen cyclic orientations, because the incidence graph is a tree and any excursion from a hyperedge must return through the same attachment vertex. If so, the argument can be repaired by adding an order-invariance lemma and by summing the double-counting identity over v. But as written, the proof is incomplete, so the paper should not be accepted without revision. The verdict CONDITIONAL matches the reader's assessment: the central claim is plausible and probably correct, but the reconstruction step needs a rigorous justification. My concrete test would settle the ambiguity by checking order-invariance on a small example and confirming the deck-based computation via the summed identity.","tokens_in":10701,"tokens_out":27752,"duration_ms":265329,"concrete_test":"Take a small k-uniform hypergraph where the walk tree is not obviously order-independent, e.g., H = K_4^{(3)} with root 1 (Example 2.8). Compute d_H(1,ℓ,m) for ℓ = 3,6,9 and all m under two different vertex linear orderings, say 1<2<3<4 and 1<3<2<4, by enumerating conflict-free walks and the digraph D(H,1). If the two orderings produce different values of d_H(1,ℓ,m), the proof's reconstruction step fails. If they agree, test the full reconstruction claim by summing the double-counting identity over all v: verify that (n−m choose n′−m)·Σ_v d_H(v,ℓ,m) equals Σ_{H'∈C(H,n′)} Σ_{w∈V(H')} d_{H'}(w,ℓ,m), and confirm the latter is computable from the unlabeled deck; this would show the proof can be repaired by adding an explicit lemma that the paper currently omits.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The reconstruction step in Section 4 is not justified as written. The quantity d_{H'}(v,ℓ,m) is defined through conflict-free walks (Definition 2.5), which depend on a strict linear ordering of V(H'), and via the walk tree T(H',v) built from that ordering. Meanwhile, C(H,n') is a multiset of unlabeled induced subhypergraphs: it carries no vertex orderings and no distinguished vertex v. The double-counting identity (n−m choose n′−m)·d_H(v,ℓ,m) = Σ_{H'} d_{H'}(v,ℓ,m) sums over induced H' containing a specific labeled vertex v, but from the unlabeled deck one cannot tell which vertex of each H' is v, nor which ordering to use when computing d_{H'}(v,ℓ,m). The paper does not prove that the relevant sums are independent of the ordering, nor does it sum the identity over all v so that only the deck-computable quantities Σ_w d_{H'}(w,ℓ,m) appear. Consequently, the sentence 'Therefore, from C(H,n'), we derive the matching polynomial' does not follow from the preceding equations. A repair is plausible: sum the double-counting identity over v and prove order-invariance of Σ_w d_{H'}(w,ℓ,m), but neither step is present in the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims that for every n-vertex k-uniform hypergraph H, the matching polynomial m_k(H,x) is uniquely determined by the multiset of induced subhypergraphs on n' = floor((k-1)n/k)+1 vertices (Theorem 1.4), generalizing Godsil's theorem for graphs. The proof combines the hypergraph Godsil identity (Theorem 2.7, from the second author's earlier paper [9]) with a matching/characteristic-polynomial equality for k-trees (Lemma 3.2) and a closed-walk double-counting argument in Section 4. The paper also derives a corollary on reconstructing F-tiling polynomials (Corollary 1.6) and constructs aligned/misaligned teeth hypergraphs to show the stated deck size is best possible (Theorem 5.1).","tokens_in":10961,"tokens_out":28616,"duration_ms":257279,"significance":"If the proof were complete, Theorem 1.4 would be a notable result: it extends Godsil's half-deck reconstruction of matching polynomials to all uniformities, despite the known failure of the hypergraph reconstruction conjecture for k >= 3. The use of the second author's hypergraph Godsil identity as a tool is legitimate, and the closed-walk machinery is well chosen. However, the manuscript currently has load-bearing gaps: the passage from the unlabeled deck to the double-counting sums is unjustified, the proof of Lemma 3.2 relies on a false structural assertion about k-trees, and the sharpness construction in Section 5 contains serious errors. With substantial revision the approach may be salvageable, but as written I cannot regard the main claims as proved.","major_comments":[{"comment":"The step from the double-counting identity to deck-computability is not justified. The quantity d_{H'}(v,ell,m) is defined through conflict-free walks (Definitions 2.5 and 2.6) and hence depends on a strict linear ordering of the vertices of H' and on the choice of a distinguished vertex v, via the digraph D(H',v). The identity (n-m choose n'-m) d_H(v,ell,m) = sum_{H'} d_{H'}(v,ell,m) sums over induced subhypergraphs H' that contain the fixed labeled vertex v of the original H. The deck C(H,n') is a multiset of unlabeled induced subhypergraphs: it supplies neither a vertex ordering for each H' nor the identity of v inside each copy. Consequently the sentence 'Therefore, from C(H,n'), we derive the matching polynomial' does not follow. A repair would require summing the identity over all v and proving that sum_{w in V(H')} d_{H'}(w,ell,m) is independent of the ordering chosen for H'; neither step appears in the manuscript.","section":"§4, proof of Theorem 1.4"},{"comment":"The proof of Lemma 3.2 begins with the assertion that every k-tree contains a hyperedge e in which all but one vertex have degree one. This is false for k-trees as defined in §2.1 (k-graphs with no Berge-cycle). For instance, the 3-uniform hypergraph with edges {a,b,c}, {b,d,e}, and {a,f,g} has no Berge-cycle and no hyperedge with two degree-one vertices. The induction in the lemma requires the k-1 vertices other than the chosen vertex v to be leaves so that Lemma 2.2 can delete their incident arcs, so the proof as written collapses. Since Lemma 3.2 is used in §4 to replace the matching polynomial of the walk tree by the characteristic polynomial of the associated digraph, this gap is load-bearing.","section":"§3, Lemma 3.2"},{"comment":"The proof of Theorem 5.1 does not define a valid bijection eta. For a subset J of V(H1) with |J|=s, the image must be a subset of V(H2) of size s. In Case 1, eta(J)=X1 union phi(J\\X1) is a subset of V(H2) but has size |X1|+|J\\X1|=|J|+|X1\\J|, which exceeds |J| whenever X1 is not contained in J. In Case 2, eta(J)=(J\\X2) union phi(X2) mixes vertices of H1 (from J\\X2) with vertices of H2 (from phi(X2)), so it is not even a subset of V(H2) in general. These flaws invalidate the equality C(H1,s)=C(H2,s) as proved. Moreover, X2 is defined using the nonexistent edge e_{ell+1} of AT(k,ell). The sharpness theorem therefore needs a corrected proof.","section":"§5, proof of Theorem 5.1"}],"minor_comments":[{"comment":"The formula for V(f_j) uses b_{j-1}, but the vertex set of MT(k,ell) begins at b_1; this appears to be a typo, since the proof's isomorphism claim for phi depends on the corrected indexing f_j={b_j,c_j,b_{j+1}}.","section":"§5, Definition 5.3"},{"comment":"The set X2 is defined using the edge e_{ell+1}, which does not exist in AT(k,ell); it should presumably refer to a defined edge such as e_ell.","section":"§5, proof of Theorem 5.1"},{"comment":"There are several typos: 'uni form' in the abstract, 'desried' in the proof of Lemma 3.3, and 'algined/misalgined' in Figure 3; these should be corrected in revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main result is promising and the approach is likely repairable, but the gaps in §3, §4, and §5 are substantial. In particular, the deck step in §4 is not a minor exposition issue; it is the central reconstruction argument. The editor may wish to invite a revision with a careful treatment of order-invariance under vertex relabeling and a corrected proof of the sharpness construction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the take: this is a real result, and I think it's correct, but the proof of Theorem 1.4 has a gap that needs filling before I'd call it fully rigorous.\n\nThe paper proves a genuinely new generalization of Godsil's 1981 theorem: for every k-uniform hypergraph on n vertices, the matching polynomial is determined by the deck of induced subhypergraphs on floor((k-1)/k n)+1 vertices. That's surprising given Kocay's counterexamples to full hypergraph reconstruction for k≥3. The proof strategy is elegant: use the second author's hypergraph Godsil identity to express matching polynomial ratios as generating functions of closed walks in a digraph attached to each vertex, then double-count those walks. The F-tiling corollary is a clean application, and the sharpness construction with aligned/misaligned teeth is natural and extends the Spinoza-West example.\n\nThe soft spot is in Section 4. The double-counting identity (n-m choose n'-m) d_H(v,ℓ,m) = Σ_{H'} d_{H'}(v,ℓ,m) is fine for a fixed labeled v, but the deck C(H,n') is unlabeled. You can't identify v in each H', and the paper doesn't sum over v to get the power sums that determine the matching polynomial. Additionally, d_{H'}(v,ℓ,m) depends on a linear ordering of V(H') via the conflict-free walk definition, and the paper never shows the relevant sum over vertices is ordering-independent. I think both issues are fixable—sum the identity over v, and prove order-invariance, probably through inclusion-exclusion on vertex subsets—but the leap as written isn't justified.\n\nThe sharpness section is compressed: the bijection η is asserted to be bijective but no proof is given. Given the case analysis, that needs checking. There's also a typo: X2 := V(e_{ℓ+1}) - {u_ℓ} doesn't make sense since edges only go up to e_ℓ.\n\nBottom line: the core idea is sound, the result is worth having, and the reliance on the second author's earlier identity is legitimate—it's a separate theorem, not a circular dependency. I'd send this to a serious referee, with the request to fix the reconstruction step and prove the bijection. The authors have something important here.","headline":"Real and likely correct generalization of Godsil's matching polynomial reconstruction, but with a fillable gap in the deck-to-polynomial step and an unproved bijection in the sharpness section.","tokens_in":11494,"tokens_out":8466,"would_cite":true,"duration_ms":72263,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05C31","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"The matching polynomial of every k-uniform hypergraph is uniquely determined by its induced subhypergraphs on floor((k-1)n/k)+1 vertices.","keywords":["matching polynomial","hypergraph reconstruction","k-uniform hypergraph","induced subhypergraphs","closed walks","walk-tree identity","F-tiling polynomial","sharpness construction"],"falsifier":"Search for two n-vertex k-uniform hypergraphs with identical decks $C(H, \\lfloor (k-1)n/k\\rfloor+1)$ but different matching polynomials; Theorem 1.4 predicts none exists. A cheaper local test: compute the vertex-ordered walk tallies $d_{H'}(v,\\ell,m)$ for a small hypergraph $H'$ under two different vertex orderings and check whether the sums over the unlabeled deck are invariant; any mismatch would pinpoint a gap in the double-counting step.","tokens_in":10488,"feed_emoji":"🧩","tokens_out":8864,"duration_ms":74419,"temperature":0.7,"pith_summary":"An n-vertex k-uniform hypergraph's matching polynomial—whose coefficients count matchings of each size—is uniquely determined by the multiset of induced subhypergraphs on $\\lfloor (k-1)n/k\\rfloor+1$ vertices. The paper proves this for every $n \\geq k \\geq 2$, extending the classical 1981 result for graphs to all uniform hypergraphs. The same argument yields a corollary: for any fixed k-vertex graph F, the F-tiling polynomial of an n-vertex graph is reconstructible from induced subgraphs on the same fraction of vertices, so the number of F-factors is too. The paper also constructs hypergraphs showing that the fraction $(k-1)/k$ is best possible whenever n is divisible by k.","feed_headline":"A (k-1)/k vertex deck fixes every hypergraph matching polynomial","feed_subtitle":"Reconstructs any k-uniform hypergraph's matching polynomial from about (k-1)/k of its vertices; the bound is sharp.","key_machinery":"The load-bearing object is the rooted k-walk-tree $T(H,v)$: its vertices are the conflict-free walks starting at $v$, and its hyperedges are formed by extending such walks through a hyperedge of $H$. The hypergraph analogue of the classical walk-tree identity (Theorem 2.7) says $m_k(H-v,x)/m_k(H,x) = m_k(T(H,v)-(v),x)/m_k(T(H,v),x)$. A second identity (Lemma 3.2) converts matching polynomials of ordered k-trees into characteristic polynomials of digraphs: each hyperedge with ordered vertices $w_1,\\ldots,w_k$ becomes the directed cycle $w_1 \\to w_2 \\to \\cdots \\to w_k \\to w_1$. Together with the closed-walk generating function of a digraph, this makes the logarithmic derivative of $m_k(H,x)$ equal to the sum over all vertices of the closed-walk counts in $D(H,v)$. The support bound $|\\pi(V(C))| \\leq \\lfloor (k-1)|E(C)|/k\\rfloor+1$ for a closed walk $C$ is what reduces the needed data to induced subhypergraphs on $n'$ vertices.","core_discovery":"The central claim is Theorem 1.4: if two n-vertex k-uniform hypergraphs have the same multiset of induced subhypergraphs on $n' = \\lfloor (k-1)n/k\\rfloor+1$ vertices, then they have the same matching polynomial $m_k(H,x)$. Its proof starts from the hypergraph analogue of the classical walk-tree identity, which expresses the ratio $m_k(H-v,x)/m_k(H,x)$ as the same ratio for a rooted k-walk-tree $T(H,v)$. For a k-tree whose hyperedges carry an ordering, the matching polynomial equals the characteristic polynomial of the associated digraph (each hyperedge becomes a directed cycle), and the logarithmic derivative of $m_k(H,x)$ then equals the generating function of closed walks in these digraphs, summed over all vertices. A support lemma bounds the number of vertices visited by a closed walk of length $\\ell$ by $\\lfloor (k-1)\\ell/k\\rfloor+1$, which is exactly why the deck of size $n'$ suffices: every closed-walk count needed to determine the power sums of the roots—hence the polynomial via the standard power-sum identities—can be recovered from that deck by double counting. The final section gives aligned- and misaligned-'teeth' hypergraphs that share the deck of size $\\lfloor (k-1)n/k\\rfloor$ but have different matching polynomials, proving the threshold is sharp for n divisible by k.","pith_inferences":["The closed-walk support bound is the engine here; the same mechanism could plausibly reconstruct other polynomials whose coefficients count spanning structures, provided a comparable bound on the vertex set visited by the relevant walks can be proved.","The double-counting step in §4 assumes the unlabeled deck supplies the ordered-walk tallies $d_{H'}(v,\\ell,m)$; since the deck carries no vertex ordering, the cleanest way to test this step is to compute these tallies for one small hypergraph under two different orderings and see whether the aggregated sums agree.","For F-tilings with F not a single edge, the optimal fraction may be smaller than $(k-1)/k$; the paper's Problem 6.1 asks for the best constant $c_F$, and the teeth construction suggests how to hunt for lower bounds.","The paper's conjectured analogue for Hamilton cycles would follow from a walk bound in a suitable auxiliary digraph, so a natural next step is to search for such a bound."],"forward_implications":["For any k-uniform hypergraph, the number of matchings of every size—including perfect matchings—can be read off from induced subhypergraphs on $\\lfloor (k-1)n/k\\rfloor+1$ vertices.","For any fixed k-vertex graph F, the F-tiling polynomial, and in particular the number of perfect F-tilings (F-factors), is reconstructible from induced subgraphs on the same fraction of vertices.","The threshold $\\lfloor (k-1)n/k\\rfloor+1$ is best possible for all n divisible by k: the aligned- and misaligned-teeth constructions share the smaller deck but differ in whether they have a perfect matching.","The proof supplies an alternative derivation of the sharpness example for ordinary graphs, via the same explicit bijection between vertex subsets.","Because full hypergraph reconstruction fails for every uniformity $k \\geq 3$, this shows matching polynomials are a well-behaved exception: a linear-size fraction of the vertex set, rather than almost all of it, determines all matching counts."],"supporting_citations":[{"why":"Establishes the graph case (matching polynomial reconstructible from $\\lfloor n/2\\rfloor+1$ induced subgraphs) and the walk-tree identity that the hypergraph analogue extends.","marker":"[3]"},{"why":"Supplies the hypergraph analogue of the walk-tree identity and the k-walk-tree construction used as the starting point of the proof.","marker":"[9]"},{"why":"Provides the graph sharpness example that the teeth constructions extend and reprove.","marker":"[11]"},{"why":"Used for the classical fact that the matching polynomial of a tree equals its characteristic polynomial, which Lemma 3.2 generalizes to ordered k-trees.","marker":"[4]"},{"why":"Gives the undirected version of the closed-walk generating function that underlies the walk-counting step.","marker":"[5]"},{"why":"Provides the deletion-contraction recursion for hypergraph matching polynomials used in Lemma 2.4 and in the induction for Lemma 3.2.","marker":"[12]"}],"fun_headline_variants":["Sharp bound: (k-1)/k vertex deck fixes hypergraph matchings","Godsil's theorem generalized: hypergraphs from partial decks","From (k-1)/k vertices, read off every hypergraph matching polynomial","Reconstruction threshold: (k-1)/k vertices determine hypergraph matchings","Matching polynomial of any k-graph from (k-1)/k of its vertices"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the multiset of unlabeled induced subhypergraphs on $\\lfloor (k-1)n/k\\rfloor+1$ vertices determines the double-counted closed-walk tallies $d_{H'}(v,\\ell,m)$, even though those tallies are defined using an arbitrary ordering of each subhypergraph's vertices and the deck itself carries no ordering information.","fun_headline_variants_meta":{"raw":{"variants":["Sharp bound: (k-1)/k vertex deck fixes hypergraph matchings","Godsil's theorem generalized: hypergraphs from partial decks","From (k-1)/k vertices, read off every hypergraph matching polynomial","Reconstruction threshold: (k-1)/k vertices determine hypergraph matchings","Matching polynomial of any k-graph from (k-1)/k of its vertices"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0004,"raw_usage":{"total_tokens":2119,"prompt_tokens":1007,"completion_tokens":1112,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":623,"completion_tokens_details":{"reasoning_tokens":1009}},"tokens_in":623,"tokens_out":1112,"duration_ms":8713,"temperature":1.0,"reasoning_tokens":1009,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T21:24:02.766463+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for two n-vertex k-uniform hypergraphs with identical decks $C(H, \\lfloor (k-1)n/k\\rfloor+1)$ but different matching polynomials; Theorem 1.4 predicts none exists. A cheaper local test: compute the vertex-ordered walk tallies $d_{H'}(v,\\ell,m)$ for a small hypergraph $H'$ under two different vertex orderings and check whether the sums over the unlabeled deck are invariant; any mismatch would pinpoint a gap in the double-counting step.","supporting_citations":[{"cited_title":"Matchings and walks in graphs","cited_arxiv_id":null,"evidence_quote":"Establishes the graph case (matching polynomial reconstructible from $\\lfloor n/2\\rfloor+1$ induced subgraphs) and the walk-tree identity that the hypergraph analogue extends."},{"cited_title":"Reconstruction from th e deck of k-vertex induced sub- graphs","cited_arxiv_id":null,"evidence_quote":"Provides the graph sharpness example that the teeth constructions extend and reprove."},{"cited_title":"On the theory of the matching polynomial","cited_arxiv_id":null,"evidence_quote":"Used for the classical fact that the matching polynomial of a tree equals its characteristic polynomial, which Lemma 3.2 generalizes to ordered k-trees."},{"cited_title":"Spectral conditions for the reconstructibility of a graph","cited_arxiv_id":null,"evidence_quote":"Gives the undirected version of the closed-walk generating function that underlies the walk-counting step."},{"cited_title":"The matching polynomials and spectral radii of uniform supertrees","cited_arxiv_id":null,"evidence_quote":"Provides the deletion-contraction recursion for hypergraph matching polynomials used in Lemma 2.4 and in the induction for Lemma 3.2."}],"review_version":1}