Reconstructing hypergraph matching polynomials

Donggyu Kim; Hyunwoo Lee

REVIEW 3 major objections 3 minor 14 references

Reconstructing hypergraph matching polynomials

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

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

Pith's one-line read The matching polynomial of every k-uniform hypergraph is uniquely determined by its induced subhypergraphs on floor((k-1)n/k)+1 vertices.

desk verdict 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. read the letter →

arxiv 2501.19081 v1 pith:E2TFK47E submitted 2025-01-31 math.CO

Donggyu Kim , Hyunwoo Lee This is my paper · ORCID

classification math.CO MSC 05C6505C3105C70

keywords matchingpolynomialhypergraphreconstructionk-uniforminducedsubhypergraphsclosedwalkswalk-treeidentityF-tilingsharpnessconstruction

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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.

Desk Editor's Note

read the 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.

The 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.

The 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.

The 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_ℓ.

Bottom 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.

Referee Report

3 major / 3 minor

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).

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 (3)

[§4, proof of Theorem 1.4] 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.
[§3, Lemma 3.2] 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.
[§5, proof of Theorem 5.1] 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.

minor comments (3)

[§5, Definition 5.3] 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}}.
[§5, proof of Theorem 5.1] 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.
[Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof has an unlabeled-deck gap, but the result does not reduce to its inputs by construction.

full rationale

The paper's central derivation is not circular. Theorem 1.4 is obtained by expressing the matching polynomial through power sums of its roots, then through closed-walk counts in the digraph D(H,v), and finally through a double-counting identity over induced subhypergraphs. The hypergraph Godsil identity (Theorem 2.7) is imported from the second author's earlier paper [9], but it is a separately stated and proved identity whose assumptions do not include the reconstruction claim of the present paper; using it as a tool does not make the argument circular. Lemma 3.2 is proved in-line, and the Newton-identity step is standard. The only serious issue is the final inference from the double-counting identity: the quantities d_{H'}(v,ell,m) are defined for a labeled vertex v and require a linear ordering of the vertices of H', while C(H,n') is a multiset of unlabeled induced subhypergraphs. The paper does not prove that the relevant sums can be computed from the unlabeled deck. That is a correctness gap in the proof, not a circular reduction of the theorem to its inputs. No equation in the paper is equivalent by construction to the input deck, and no fitted parameter is renamed as a prediction. Therefore the circularity score is 0.

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

No free parameters fitted to data. The paper relies on one imported theorem (hypergraph Godsil identity from [9]), standard linear algebra lemmas, and a structural assumption that each hypergraph carries a vertex ordering. No new physical or mathematical entities are postulated; the walk-tree and digraph D(H,v) are proof constructs, not entities the central claim depends on independently.

assumptions (4)

domain assumption Hypergraph Godsil's identity (Theorem 2.7): m_k(H-v,x)/m_k(H,x) = m_k(T(H,v)-V,x)/m_k(T(H,v),x), where T(H,v) is the conflict-free walk tree.
Imported from the second author's prior paper [9]; it is the key tool and is not proved in this paper. The paper notes it extends to multi-edges.
standard math Folklore generating function for closed walks in a digraph (Lemma 2.3): 1/x * chi(D-v, x^{-1})/chi(D,x^{-1}) is the generating function of closed walks starting at v.
Proved in the paper from (I - xA)^{-1} and cofactor formulas; standard linear algebra over the reals.
standard math Recursive formula for hypergraph matching polynomial (Lemma 2.4): m_k(H,x) = x * m_k(H-v,x) - sum_e m_k(H-V(e),x).
Cited from Su et al. [12, Theorem 7(c)]; follows directly from the definition of matching polynomial.
domain assumption Every hypergraph is equipped with a strict linear ordering of its vertices (Section 2.1).
The conflict-free walk tree and the digraph D(H,v) are defined using this ordering. The theorem's conclusion, matching polynomial reconstruction, is about unordered hypergraphs, so the proof must handle the ordering dependence of intermediate quantities.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Reconstructing hypergraph matching polynomials." pith.science (2026). https://pith.science/paper/E2TFK47E

@misc{pith2026250119081,
  author       = {Pith},
  title        = {Pith review of: Reconstructing hypergraph matching polynomials},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E2TFK47E}},
  note         = {Machine review of arXiv:2501.19081}
}

abstract

By utilizing the recently developed hypergraph analogue of Godsil's identity by the second author, we prove that for all $n \geq k \geq 2$, one can reconstruct the matching polynomial of an $n$-vertex $k$-uniform hypergraph from the multiset of all induced sub-hypergraphs on $\lfloor \frac{k-1}{k}n \rfloor + 1$ vertices. This generalizes the well-known result of Godsil on graphs in 1981 to every uniform hypergraph. As a corollary, we show that for every graph $F$, one can reconstruct the number of $F$-factors in a graph under analogous conditions. We also constructed examples that imply the number $\lfloor \frac{k-1}{k}n \rfloor + 1$ is the best possible for all $n\geq k \geq 2$ with $n$ divisible by $k$.

Figures

Figures reproduced from arXiv: 2501.19081 by the authors.

**Figure 1.** T (K (3) 4 , 1). Example 2.8. Let H = K (3) 4 be the complete 3-graph on four vertices 1, 2, 3, 4 with the usual linear ordering. We denote by ei the edge missing a vertex i. Then T (H, 1) is a linear 3-graph illustrated in [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 2.** A linear hypergraph L and the corresponding digraph D(L). Lemma 3.2. Let T be a k-tree endowed with a linear ordering of the vertices of each hyperedge, and let D = D(T ). Then mk(T, x) = χ(D, x). 5 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Aligned/misaligned-(3, 4)-teeth. Definition 5.2. An aligned-(k, ℓ)-teeth AT (k, ℓ) is a k-graph such that the vertex set is {u0, . . . , uℓ+1} ∪ [ ℓ i=0 {c 1 i , . . . , ck−2 i } ∪ {b1, . . . , bℓ}, and the edge set is {e0, . . . , eℓ} ∪ {f1, . . . , fℓ−1}, where V (ei) = {ui , c1 i , . . . , ck−2 i , ui+1} and V (fj ) = {bj, c1 j , . . . , ck−2 j , bj+1} for each 0 ≤ i ≤ ℓ and 1 ≤ j ≤ ℓ − 1. Definition 5.3. A misal… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

[9]

Random matchings in linear hypergraphs

Hyunwoo Lee. “Random matchings in linear hypergraphs”. arXiv:2406.06421. 2024

arXiv 2024
[1]

Almost every graph has reconstruction number three

B´ ela Bollob´ as. “Almost every graph has reconstruction number three”. In: J. Graph Theory 14.1 (1990), pp. 1–4

work page 1990
[2]

On Ulam’s conjecture for separable graphs

John A. Bondy. “On Ulam’s conjecture for separable graphs”. I n: Paciﬁc J. Math. 31 (1969), pp. 281–288

work page 1969
[3]

Matchings and walks in graphs

Chris D. Godsil. “Matchings and walks in graphs”. In: J. Graph Theory 5.3 (1981), pp. 285–297

work page 1981
[4]

On the theory of the matching polynomial

Chris D. Godsil and Ivan Gutman. “On the theory of the matching polynomial”. In: J. Graph Theory 5.2 (1981), pp. 137–144

work page 1981
[5]

Spectral conditions for the reconstructibility of a graph

Chris D. Godsil and Brendan D. McKay. “Spectral conditions for the reconstructibility of a graph”. In: J. Combin. Theory Ser. B 30.3 (1981), pp. 285–289

work page 1981
[6]

A survey of the reconstruction conjecture

Frank Harary. “A survey of the reconstruction conjecture” . In: Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973). Vol. 406. Lecture Notes in Math. Springer, Berlin-New York, 1974, pp. 18–28

work page 1973
[7]

A congruence theorem for trees

Paul J. Kelly. “A congruence theorem for trees”. In: Paciﬁc J. Math. 7 (1957), pp. 961–968

work page 1957

Show all 14 references

[8]

A family of nonreconstructible hypergraphs

William L. Kocay. “A family of nonreconstructible hypergraphs”. I n: J. Combin. Theory Ser. B 42.1 (1987), pp. 46–63

1987
[10]

Reconstructibility and perfect graphs

Michael von Rimscha. “Reconstructibility and perfect graphs” . In: Discrete Math. 47.2-3 (1983), pp. 283–291

1983
[11]

Reconstruction from th e deck of k-vertex induced sub- graphs

Hannah Spinoza and Douglas B. West. “Reconstruction from th e deck of k-vertex induced sub- graphs”. In: J. Graph Theory 90.4 (2019), pp. 497–522

2019
[12]

The matching polynomials and spectral radii of uniform supertrees

Li Su, Liying Kang, Honghai Li, and Erfang Shan. “The matching polynomials and spectral radii of uniform supertrees”. In: Electron. J. Combin. 25.4 (2018), Paper No. 4.13, 24

2018
[13]

All the king’s horses. A guide to reconstruction

William T. Tutte. “All the king’s horses. A guide to reconstruction ”. In: Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) , pp. 15–33

1977
[14]

Ulam.A collection of mathematical problems

Stanis/suppress law M. Ulam.A collection of mathematical problems . Vol. no. 8. Interscience Tracts in Pure and Applied Mathematics. Interscience Publishers, New York-Lond on, 1960, pp. xiii+150. 11

1960

Pith tools

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

[1] [9]

Random matchings in linear hypergraphs

Hyunwoo Lee. “Random matchings in linear hypergraphs”. arXiv:2406.06421. 2024

arXiv 2024

[2] [1]

Almost every graph has reconstruction number three

B´ ela Bollob´ as. “Almost every graph has reconstruction number three”. In: J. Graph Theory 14.1 (1990), pp. 1–4

work page 1990

[3] [2]

On Ulam’s conjecture for separable graphs

John A. Bondy. “On Ulam’s conjecture for separable graphs”. I n: Paciﬁc J. Math. 31 (1969), pp. 281–288

work page 1969

[4] [3]

Matchings and walks in graphs

Chris D. Godsil. “Matchings and walks in graphs”. In: J. Graph Theory 5.3 (1981), pp. 285–297

work page 1981

[5] [4]

On the theory of the matching polynomial

Chris D. Godsil and Ivan Gutman. “On the theory of the matching polynomial”. In: J. Graph Theory 5.2 (1981), pp. 137–144

work page 1981

[6] [5]

Spectral conditions for the reconstructibility of a graph

Chris D. Godsil and Brendan D. McKay. “Spectral conditions for the reconstructibility of a graph”. In: J. Combin. Theory Ser. B 30.3 (1981), pp. 285–289

work page 1981

[7] [6]

A survey of the reconstruction conjecture

Frank Harary. “A survey of the reconstruction conjecture” . In: Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973). Vol. 406. Lecture Notes in Math. Springer, Berlin-New York, 1974, pp. 18–28

work page 1973

[8] [7]

A congruence theorem for trees

Paul J. Kelly. “A congruence theorem for trees”. In: Paciﬁc J. Math. 7 (1957), pp. 961–968

work page 1957