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


Andrea Frosini, University of Florence. 18 janvier 2024 10:00 TLR limd
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.