On P-unique hypergraphs

Abstract

We study hypergraphs which are uniquely determined by their chromatic, independence and matching polynomials. B. Bollobás, L. Pebody and O. Riordan (2000) conjectured (BPR-conjecture) that almost all graphs are uniquely determined by their chromatic polynomials. We show that for $r$-uniform hypergraphs with $r\ge 3$ this is almost never the case. This disproves the analolgue of the BPR-conjecture for $3$-uniform hypergraphs. For $r=2$ this also holds for the independence polynomial, as shown by J.A. Makowsky and V. Rakita (2017), whereas for the chromatic and matching polynomial this remains open.

10 pages