The polytope of degree sequences of hypergraphs Original Research Article

Let Dn(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope Dn(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes Dn(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on Dn(2). Our main results concern the extreme points and facets of Dn(r). We characterize adjacency of extreme points of Dn(r) and, in the case r=2, determine the distance between two given vertices in the graph of Dn(2). We give a characterization of when a linear inequality determines a facet of Dn(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of Dn(2); find an explicit family of Erdös–Gallai type facets of Dn(r); and describe a simple lifting procedure that produces a facet of Dn+1(r) from one of Dn(r).