On the reconstruction of 3-uniform hypergraphs from unique degree sequences


Andrea Frosini, University of Florence. Jan. 18, 2024, 10 a.m. TLR limd 2:00:00
Abstract:

We consider the problem of detecting and reconstructing degree sequences of 3-uniform hypergraphs. The problem is known to be NP-hard, so some subclasses are inspected in order to detect instances that admit a P-time reconstruction algorithm. Here, I consider instances having specific numerical patterns and I show how to easily reconstruct them.