5
$\begingroup$

Consider the set of all graphic sequences with $n$ elements as a subset of $\mathbb{R}^{n}$, namely let $$D(n)=\{(d_{1},\dots,d_{n})\in\mathbb{Z}_{+}^{n}:d_{1}\geq\dots\geq d_{n},\ \sum_{i=1}^{n}d_{i}\ \text{is even},\ \sum_{i=1}^{k}d_{i}\leq k(k-1)+\sum_{i=k+1}^{n}\min\{k,d_{i}\}\ \text{for all}\ 1\leq k\leq n \}.$$ One can observe that the diameter of $D(n)$ equals $(n-1)\sqrt[]{n}$. The question is:

How to compute the volume of the convex hull of $D(n)$?

$\endgroup$
2
$\begingroup$

The polytope considered by Richard Stanley is the polytope of degree sequences. Sergiy Kozerenko's question is about the polytope of degree partitions for which see paper R46 of Volume 13 (2006) of the Electronic Journal of combinatorics. It is shown there that the volume of the polytope of degree sequences is n! times the volume of the polytope of degree partitions.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for this observation. When I said that the question of Kozerenko seems to be much more difficult, I was actually thinking of the number of integer points, not the volume. $\endgroup$ – Richard Stanley Dec 4 '15 at 22:25
4
$\begingroup$

This is worked out in section 3 of Stanley's paper "A Zonotope Associated with Graphical Degree Sequences". The answer is $$\operatorname{Vol}(D(n))=\sum_{X}2^{c(X)}$$ where $X$ ranges through all graphs whose connected components contain a unique cycle, which is of odd length, and $c(X)$ is the number of odd cycles.

$\endgroup$
1
  • 2
    $\begingroup$ Actually, I compute the volume of the convex hull of all ordered degree sequences of length $n$, that is, I don't assume $d_1\leq d_2\leq \cdots \leq d_n$. The question of Kozerenko is completely different and seems to be much more difficult. $\endgroup$ – Richard Stanley Nov 5 '15 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.