| Popis: |
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 concern the extreme points and facets of D-n (r). We characterize adjacency of extreme points of D-n (r) and, in the case r = 2, determine the distance between two given vertices in the graph of D-n (2). We give a characterization of when a linear inequality determines a facet of D-n (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 D-n(2); find an explicit family of Erdos-Gallai type facets of D-n (r); and describe a simple lifting procedure that produces a facet of Dn+1 (r) from one of D-n (r). (C) 2002 Elsevier Science Inc. . |
