On the degree sequence of 3-uniform hypergraph
Andrea Frosini  1  , Christophe Picouleau  2  
1 : Università di Firenze
2 : Centre d'études et de recherche en informatique et communications
Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise : EA4629, Conservatoire National des Arts et Métiers [CNAM] : EA4629

The study of the degree sequences of h-uniform hypergraphs, say h-sequences, was a longstanding open problem in the case of h > 2, until very recently where its decision version was proved to be NP-complete. Formally, the decision version of this problem is: Given π = (d 1 , d 2 , . . . , d n ) a non increasing sequence of positive integers, is π the degree sequence of a h-uniform simple hypergraph? Now, assuming P = ̸NP, we know that such an effective characterization cannot exist even for the case of 3-uniform hypergraphs. However, several necessary or sufficient conditions can be found in the literature; here, relying on a result of S. Behrens et al., we present a sufficient condition for the 3-graphicality of a degree sequence and a polynomial time algorithm that realizes one of the associated 3-uniform hypergraphs, if it exists. Both the results are obtained by borrowing some mathematical tools from discrete tomography, a quite recent research area involving discrete mathematics, discrete geometry and combinatorics.


Online user: 1