The polytope of degree partitions

Amitava Bhattacharya, UI-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,\ldots ,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.