The polytope of degree sequences of hypergraphs |
| |
Authors: | N. L. Bhanu Murthy Murali K. Srinivasan |
| |
Affiliation: | Department of Mathematics, Indian Institute of Technology, Bombay, Powai, Mumbai 400 076, India |
| |
Abstract: | 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). |
| |
Keywords: | Degree sequences Hypergraphs Polytopes Threshold graphs Threshold sequences |
本文献已被 ScienceDirect 等数据库收录! |
|