The Polytope of Degree Sequences of Hypergraphs
by
N.L. Bhanumurthy
Department of Mathematics,Indian Institute of Technology-Bombay, India
Coauthors: Murali K. Srinivasan (Department of Mathematics,Indian Institute of Technology-Bombay, India)

Let D(n, r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set 1, 2, ..., n. The polytope D(n, 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 Erdos-Gallai inequalities. In this paper we study the polytopes D(n, r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on D(n, 2).

Our main results are : characterization of adjacency of extreme points of D(n, r); determination of the distance between two given vertices in the graph of D(n, 2); characterization of when a linear inequality determines a facet of D(n, r); a new short proof for the facets of D(n, 2); an explicit family of Erdos-Gallai type facets of D(n, r); and a facet of D(n, 3) having the Fibonacci numbers as coefficients.

Date received: October 16, 2000