Integer points in the degree-sequence polytope

Abstract

An integer vector $b\in {\mathbb{Z}}^d$ is a degree sequence if there exists a hypergraph with vertices $\{1,\dots ,d\}$ such that each $b_i$ is the number of hyperedges containing $i$. The degree-sequence polytope ${\mathcal{Z}}^d$ is the convex hull of all degree sequences. We show that all but a $2^{-\Omega (d)}$ 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^{O(d)}$ via linear programming techniques. This is substantially faster than the $2^{O(d^2)}$ running time of the current-best algorithm for the degree-sequence problem. We also show that for $d\ge 98$, the degree-sequence polytope ${\mathcal{Z}}^d$ contains integer points that are not degree sequences. Furthermore, we prove that the linear optimization problem over ${\mathcal{Z}}^d$ is $\mathrm{NP}$-hard. This complements a recent result of Deza et al. (2018) who provide an algorithm that is polynomial in $d$ and the number of hyperedges.

14 pages