Integer points in the degree-sequence polytope

An integer vector 𝑏 ∈ Z𝑑 is a degree sequence if there exists a hypergraph with vertices {1, … , 𝑑} such that each 𝑏𝑖 is the number of hyperedges containing 𝑖. The degree-sequence polytope 𝒵 𝑑 is the convex hull of all degree sequences. We show that all but a 2−𝛺(𝑑) fraction of integer vectors in the degree sequence polytope are degree sequences. Furthermore, the corresponding hypergraph of these points can be computed in time 2𝑂(𝑑) via linear programming techniques. This is substantially faster than the 2𝑂(𝑑2 ) running time of the current-best algorithm for the degree-sequence problem. We also show that for 𝑑 ⩾ 98, 𝒵 𝑑 contains integer points that are not degree sequences. Furthermore, we prove that both the degree sequence problem itself and the linear optimization problem over 𝒵 𝑑 are NP-hard. The latter complements a recent result of Deza et al. (2018) who provide an algorithm that is polynomial in 𝑑 and the number of hyperedges.