Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
4  
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 –  Benjamin Steinberg Apr 9 at 17:28

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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