1
$\begingroup$

A multipermutahedron is the convex hull of all permutations of a list of numbers. For example, $\Pi(0,1,2)$ generates a regular hexagon, and $\Pi(0,1,1,2)$ generates a cuboctahedron.

In general, given a permutahedron such as $\Pi(0,1,1,2,2,2,3,4,4,4),$ faces are determined by partitions of the ordered list with the property that parts of the partitions of length greater than $1$ contain at least two distinct elements. (See the paper The Combinatorics of Permutation Polytopes by Billera and Sarangarajan.) So $0112|2234|4|4$ determines a face, which is the product of a cuboctahedron and a truncated tetrahedron. Note that $0112|2234|44$ generates the same face, since the $44$ part degenerates to a point, so we essentially make sure there is a one-to-one correspondence between suitable partitions and faces.

I have results for many specific cases, but I have not been able to find any general results (e.g., not just looking at simple polytopes), either for the $f$-vectors or for counting this type of partition. Any pointers would be greatly appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It is easy to write down a generating function, though I don't know how useful it will be to you. The number of ordered partitions of the multiset $\{ 0^{m_0}, 1^{m_1},\dots\}$ into $k$ blocks such that each block of more than one element contains at least two distinct elements is the coefficient of $x_0^{m_0}x_1^{m_1}\cdots$ in $$ \left( \frac{1}{(1-x_0)(1-x_1)\cdots}-1-\sum_{i\geq 0}\frac{x_i^2}{1-x_i}\right)^k. $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Let me clarify with an example. Consider the $n$-dimensional simplex $0^n1.$ The number of ordered partitions into $k$ blocks should always be $1$ since there is only one type of face of a given dimension on a simplex. When I calculate the count directly using the formula above, I find that the coefficient of $x_0^nx_1$ in $((x_0+x_0^2+x_0^3+\cdots)(x_1+x_1^2+x_1^3+\cdots)+x_0+x_1)^k$ is $k$ for $k\le n+1$ rather than $1.$ When $n=4$ and $k=2,$ for example, I should only get $0|0001.$ I am not sure we are both counting the same thing. $\endgroup$
    – Vince Matsko
    Commented Apr 3, 2016 at 21:23
  • $\begingroup$ @VinceMatsko: you are right. I am counting all faces, while you are counting the different combinatorial types. $\endgroup$
    – Richard Stanley
    Commented May 3, 2016 at 23:46

You must log in to answer this question.

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