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.

Event Topic

Discrete Applied Math Seminar