The Polytope of degree partitions
Amitava Bhattacharya
Department of Mathematics, Statistics and Computer Science
University of Illinois at Chicago
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.