An algebraic approach to the reconstruction of uniform hypergraphs from their degree sequence

The reconstruction of a (hyper)graph starting from its degree sequence is one of the most relevant among the inverse problems investigated in the field of graph theory. In case of graphs, a feasible solution can be quickly reached, while in case of hypergraphs Deza et al. (2018) proved that the problem is NP-hard even in the simple case of 3-uniform ones. This result opened a new research line consisting in the detection of instances for which a solution can be computed in polynomial time. In this work we deal with 3-uniform hypergraphs, and we study them from a different perspective, exploiting a connection of these objects with partially ordered sets. More precisely, we introduce a simple partially ordered set, whose ideals are in bijection with a subclass of 3-uniform hypergraphs. We completely characterize their degree sequences in case of principal ideals (here a simple fast reconstruction strategy follows), and we furthermore carry on a complete analysis of those degree sequences related to the ideals with two generators. We also consider unique hypergraphs in Dext, i.e., those hypergraphs that do not share their degree sequence with other non-isomorphic ones. We show that uniqueness holds in case of hypergraphs associated to principal ideals, and we provide some examples of hypergraphs in Dext where this property is lost.