Reconstructing hypergraph matching polynomials

Abstract

By utilizing the recently developed hypergraph analogue of Godsil's identity by the second author, we prove that for all $n\ge k\ge 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\ge k\ge 2$ with $n$ divisible by $k$.

11 pages, 3 figures