[PFR19] On the degree sequence of 3-uniform hypergraph

Conférence Internationale avec comité de lecture : 21 st International Conference on Discrete Geometry for Computer Imagery, February 2019, pp.to appear, Series LNCS, France,

Auteurs: C. Picouleau , A. Frosini , S. Rinaldi

Mots clés: h-uniform hypergraph, hypergraph degree sequence, discrete tomography, reconstruction problem

Résumé: 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 Ï€ = (d1,d2,...,dn) a non increasing sequence of positive integers, is Ï€ the degree sequence of a h-uniform simple hypergraph? Now, assuming P Ì¸= N P , 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 re- search area involving discrete mathematics, discrete geometry and combinatorics.

BibTeX

@inproceedings {
	PFR19,
	title	=	"{On the degree sequence of 3-uniform hypergraph}",
	author	=	" C. Picouleau and A. Frosini and S. Rinaldi ",
	booktitle	=	"{21 st International Conference on Discrete Geometry for Computer Imagery}",
	year	=	2019,
	month	=	"February",
	series	=	"LNCS",
	pages	=	"to appear",
	address	=	" France",
}