7
$\begingroup$

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the permutahedron, which is defined as the convex hull of the set of vertices obtained by permuting the entries of the vector $(1,…,n)$.

An obvious generalization of the permutahedron is to consider the convex hull of all the vectors that can obtained by permuting the entries of an arbitrary vector $(a_1, \ldots, a_n) \in \mathbb{R}^n$. I would like pointers to information about the generalized permutahedron.

What if the entries of $(a_1,\ldots,a_n)$ are sampled according to a random distribution (e.g, gaussian with zero mean and some variance). This yields a random polytope. What can be said about it?

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ I think people generally use permutohedron to refer to the convex hull of all permutations of the entries of any vector with distinct entries. If the entries are distinct you always get the same face lattice, which is just the dual to the face lattice of the braid hyperplane arrangement. Maybe look at www-math.mit.edu/~apost/papers/permutohedron.pdf $\endgroup$
    – Benjamin Steinberg
    Commented Apr 9, 2014 at 17:28
  • $\begingroup$ @rnegrinho This has been inactive for a while. Did you find anything else? Thanks. $\endgroup$
    – RMurphy
    Commented Jul 15, 2019 at 0:08
  • $\begingroup$ As Nathan Reading's answer explains, the combinatorial type will with probability one be the same as the regular permutohedron. But there are other questions we could ask which seem interesting, like what is the expected volume? $\endgroup$
    – Sam Hopkins
    Commented Aug 18 at 3:41

1 Answer 1

Reset to default
8
$\begingroup$

If you're asking about the combinatorics of the polytope, then there is an easy answer. If you sample with a continuous distribution, then you will get a combinatorial permutohedron with probability 1. The only way to get something else is to take a point on one or more of the hyperplanes x_i=x_j. Then your orbit (i.e. set of vertices of the polytope) gets smaller. The simplest way to understand the number of vertices is to think about the stabilizer of your point: It is the subgroup generated by all transpositions (i j) such that your initial vector has x_i=x_j. So it's a product of symmetric groups.

Also, I agree with Benjamin Steinberg (comment above) that you want to look at the Postnikov reference.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .