2023/12/26 by Cooper, Joshua, Okur, Utku
#05C50 #05C60 (Primary) 05C31 #05C65 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2312.16152
We show that, in general, the characteristic polynomial of a hypergraph is not determined by its ``polynomial deck'', the multiset of characteristic polynomials of its vertex-deleted subgraphs, thus settling the ``polynomial reconstruction problem'' for hypergraphs in the negative. The proof proceeds by showing that a construction due to Kocay of an infinite family of pairs of 3-uniform hypergraphs which are non-isomorphic but share the same hypergraph deck, in fact, have different characteristic polynomials. The question remain unresolved for ordinary graphs.