New sufficient conditions on the degree sequences of uniform hypergraphs

The study of the degree sequences of k-uniform hypergraphs, usually called k-sequences, has been a longstanding open problem for the case of k>2, and the corresponding decision version was proved to be NP-complete recently in 2018 [15]. The problem can be formalized as follows: Given a non decreasing sequence of positive integers π=(d1,d2,…,dn), can π be the degree sequence of a k-uniform simple hypergraph? If the answer is positive, then the sequence π is said to be k-graphic. For k=2, that is for simple graphs, Erdös and Gallai [16] provided a characterization of the sequences that are 2-graphic (or simply, graphic). From this characterization, a polynomial time algorithm can be designed to reconstruct the incidence matrix of a graph having a given π as degree sequence (provided this graph exists). Due to the result of [15] and assuming P≠NP, an efficiently computable characterization like the one for k=2 does not even exist for the case of 3-uniform hypergraphs. Necessary or sufficient conditions for π to be k-graphic (k≥3) can be found in the literature. In this paper we prove some different new conditions: first we provide sufficient and also necessary conditions for the case of k-uniform and (almost) regular hypergraphs. Then, for k=3, we prove sufficient conditions in the case where π can be decomposed into π′ and π″, and π′ is graphic. Most of the results are obtained by borrowing tools from discrete tomography, a current research field on discrete mathematics.