Record Details

The polytope of degree sequences of hypergraphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title The polytope of degree sequences of hypergraphs
 
Creator MURTHY, NLB
SRINIVASAN, MK
 
Subject degree sequences
hypergraphs
polytopes
threshold graphs
threshold sequences
 
Description 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. .
 
Publisher ELSEVIER SCIENCE INC
 
Date 2011-07-27T13:25:22Z
2011-12-26T12:57:13Z
2011-12-27T05:47:10Z
2011-07-27T13:25:22Z
2011-12-26T12:57:13Z
2011-12-27T05:47:10Z
2002
 
Type Article
 
Identifier LINEAR ALGEBRA AND ITS APPLICATIONS, 350(), 147-170
0024-3795
http://dspace.library.iitb.ac.in/xmlui/handle/10054/7233
http://hdl.handle.net/10054/7233
 
Language en