The reconstruction problem of uniform hypergraphs from their degree sequences


Andrea Frosini, University of Florence. 12 janvier 2023 10:00 limd
Abstract:

The notion of hypergraph has been introduced as a generalization of graphs so that each hyperedge is a subset of the set of vertices, without constraints on its cardinality. A widely investigated problem related both to graphs and to hypergraphs concerns the characterization and reconstruction from their degree sequences. Concerning graphs, this problem has been efficiently solved in 1960 by Erdos and Gallai, while no efficient solutions are possible in the case of hypergraphs, even in the simple case of 3-uniform ones, as shown in 2018 by Deza et al. So, to reduce the NP-hard core of the hypergraph reconstruction problem, we consider a class of degree sequences defined by Deza et al. that show interesting geometrical and algebraic properties. We propose some ideas on how use those properties to challenge the related reconstruction problem.