Amitava Bhattacharya
Department of Mathematics, Statistics and Computer Science
University of Illinois at Chicago

The polytope of degree partitions

The degree partition of a simple graph is its degree sequence rearranged in weakly decreasing order. Let DP(n) (respectively, DS(n)) denote the convex hull of all degree partitions (respectively, degree sequences) of simple graphs on the vertex set [n]={1,2,...,n}. We think of DS(n) as the symmetrization of DP(n) and DP(n) as the asymmetric part of DS(n). The polytope DS(n) is a well studied object (Koren, Beissinger and Peled, Peled and Srinivasan, Stanley). In this paper we study the polytope DP(n) and determine its vertices (and, as a corollary, its volume), edges, and facets.


Friday, April 13, 3:15pm, E1 122

Last updated by skougeo AT iit DOT com on 04/03/07