CYCLOPERMUTOHEDRON

(TO NILOLAI DOLBILIN, WHO LOVES POLYTOPES)

arXiv:1401.7476v3 [math.MG] 9 Nov 2014

GAIANE PANINA

Abstract. It is known that the k-faces of the permutohedron Πn can be

labeled by (all possible) linearly ordered partitions of the set [n] = {1, ..., n}
into (n − k) non-empty parts. The incidence relation corresponds to the
refinement: a face F contains a face F ′ whenever the label of F ′ refines the
label of F .
In the paper we consider the cell complex CP n+1 defined in analogous
way, replacing linear ordering by cyclic ordering. Namely, k-cells of the
complex CP n+1 are labeled by (all possible) cyclically ordered partitions of
the set [n + 1] = {1, ..., n, n + 1} into (n + 1 − k) non-empty parts, where
(n + 1 − k) > 2. The incidence relation in CP n+1 again corresponds to the
refinement: a cell F contains a cell F ′ whenever the label of F ′ refines the
label of F .
The complex CP n+1 cannot be represented by a convex polytope, since it
is not a combinatorial sphere (not even a combinatorial manifold). However,
it can be represented by some virtual polytope (that is, Minkowski difference
of two convex polytopes) which we call ”cyclopermutohedron” CP n+1 . It
is defined explicitly, as a weighted Minkowski sum of line segments. In-
formally, the cyclopermutohedron can be viewed as ”permutohedron with
diagonals”. One of the motivations is that the cyclopermutohedron is a
”universal” polytope for moduli spaces of polygonal linkages.

1. Preliminaries
Among all famous polytopes with combinatorial backgrounds, the standard
permutohedron Πn is the oldest and probably the most important one. It
is defined (see [11]) as the convex hull of all points in Rn that are obtained
by permuting the coordinates of the point (1, 2, ..., n). It has the following
properties:
(1) Πn is an (n − 1)-dimensional polytope.
(2) The k-faces of Πn are labeled by ordered partitions of the set
[n] = {1, 2, ..., n} into (n − k) non-empty parts.
(3) In particular, the vertices are labeled by the elements of the symmetry
group Sn . For each vertex, the label is the inverse permutation of the

Key words and phrases. Permutohedron, graph-associahedron, polygonal linkage, zono-

tope, virtual polytope. UDK 514.172.45.
1
2 GAIANE PANINA

coordinates of the vertex. Two vertices are joined by an edge whenever

their labels differ by a permutation of two neighbor entries.
(4) A face F of Πn is contained in a face F ′ iff the label of F is a refinement
of the label of F ′ .
Here and in the sequel, we mean the order-preserving refinement.
For instance, ({1, 3}, {5, 6}, {4}, {2}) refines ({1, 3}, {5, 6}, {2, 4}), but
does not refine ({1, 3}, {2, 4}, {5, 6}).
(5) Each face of Πn equals the Cartesian product of standard permutohedra
of smaller dimensions.
(6) The permutohedron is a zonotope, that is, Minkowski sum of line seg-
ments.
(7) The permutohedra Π1 , Π2 , and Π3 are a one-point polytope, a segment,
and a regular hexagon respectively. The permutohedron Π4 is depicted
in Figure 1.

2314 2341

3214 3241

2431 3421
2134 3124

2143 2413 4231 4321

1234

1324 3142 4213 3412

1243 4312

1342 4123

1423 1432 4132

Figure 1. Permutahedron Π4 with labels on the vertices. The

shadowed face is labeled by ({1, 2, 3}{4}).

Historically, the permutohedron was followed by associahedron, cyclohedron

(see [11]), permutoassociahedron (see [4]), and more advanced polytopes ap-
pearing first as combinatorially described cell complexes: secondary polytope
[2], generalized associahedra [1]. The complexes luckily appeared to be com-
binatorial spheres, and moreover, representable by convex polytopes. A wider
framework includes graph-associahedra, nestohedra [10], and other recently
constructed polytopes.
In the paper, we proceed in the same manner: we first describe a cell com-
plex CP n+1 , and then show that it can be represented by a virtual polytope,
i.e., by Minkowski difference of two convex polytopes. We guess that virtual
polytopes (as the tightest algebraic generalization of convex polytopes, origi-
nally introduced in [5]) provide us a reasonable framework for this particular
complex.
 CYCLOPERMUTOHEDRON (TO NILOLAI DOLBILIN, WHO LOVES POLYTOPES) 3

The combinatorics of the complex CP n+1 almost literally repeats the com-
binatorics of permutohedron with one essential difference: linear ordering is
replaced by cyclic ordering. Thus defined, complex CP n+1 cannot be repre-
sented by a convex polytope, since it is not a combinatorial sphere (not even a
combinatorial manifold). However, it can be represented by a virtual polytope
which we call cyclopermutohedron CP n+1 . It is defined explicitly, as a weighted
Minkowski sum of line segments. The word ”weighted” means that some of
the summands are negatively weighted, that is, we take not only Minkowski
sum, but also Minkowski difference.
In an oversimplified way, the cyclopermutohedron CP n+1 can be visualized
as the permutohedron Πn ”with diagonals”. This means that all the proper
faces of Πn are also faces of CP n+1 . However, CP n+1 has some extra faces in
comparison with Πn . The latter look like ”diagonal” faces, see Figure 5.
The idea to replace linear ordering by cyclic ordering in the framework of
”famous polytopes” is not new: replacing linear ordering in the combinatorics
of associahedron yields the cyclohedron.
Although the cyclopermutohedron seems to be interesting for its own sake,
we were initially motivated by yet another application: the cyclopermutohe-
dron is a ”universal” polytope for moduli spaces of polygonal linkages. That
is, for any length assignment of a planar flexible polygon with (n + 1) edges,
its moduli space admits a natural cell structure which embeds in the (cell
structure of) the cyclopermutohedron CP n+1 .
The paper is organized as follows. Section 2 describes a regular cell complex
which we wish to realize as the face lattice of the cyclopermutohedron. Section
3 contains the construction, the main statements (Proposition 2 and Theorem
1), and low dimensional examples of the cyclopermutohedra. The main the-
orem (Theorem 1) establishes combinatorial equivalence of the cyclopermuto-
hedron and the cell complex. Next, Section 4 explains the relationship with
the moduli space of a planar polygonal linkage. The proofs of Theorem 1 and
Proposition 2 are in Section 5. To make the paper self-contained, we put all
necessary information on virtual polytopes in Section 6.

2. Cyclopermutohedron: the desired combinatorics

By a regular cell complex we mean a finite cell complex which can be
constructed inductively by defining its skeleta. The 0-skeleton is a finite set
of points endowed with discrete topology. Once the (k − 1)-skeleton is con-
structed, we attach a collection of closed k-dimensional balls Ci , called closed
cells. For each of Ci , the attaching map is a homeomorphism between ∂Ci and
a sphere homeomorphic subcomplex of the (k − 1)-skeleton.
By construction, the boundary of each closed cell has the induced structure
of a regular cell complex.
4 GAIANE PANINA

To define a regular cell complex, it suffices to list all the closed cells of the
complex together with the incidence relations. Following this rule, for a fixed
number n > 2, we define the regular cell complex CP n+1 as follows.
• For k = 0, ..., n − 2, the k-dimensional cells (k-cells, for short) of the
complex CP n+1 are labeled by (all possible) cyclically ordered parti-
tions of the set [n + 1] = {1, ..., n + 1} into (n − k + 1) non-empty
parts.
• A (closed) cell F contains a cell F ′ whenever the label of F ′ refines the
label of F . Here we mean orientation preserving refinement.
In particular, this means that the vertices of the complex CP n+1 are labeled
by cyclic orderings on the set [n + 1]. Two vertices are joined by an edge
whenever their labels differ on a permutation of two neighbor entries.

Let us first give an example, next agree how we depict the labels, and then
prove the correctness of the above construction.

{1} {4,2}
{1}

{2} {4} {3}

{3}
{2}
{1}
{1} {4}
{3} {4}
{3}
{2}

{3}
{2} {1} {4}

{3} {4}
{2}

{1} {3}
{1,2} {3}
{2} {4}

{1} {4}

Figure 2. The complex CP 4 .

Example 1. For n = 3, the complex CP n+1 = CP 4 consists of six vertices

and twelve edges. In the figure 2, all the vertices and two of the edges are
labeled.
A convention about presenting the labels. Let us agree that instead of
saying ”the cell of the complex labeled by λ” we say for short ”the cell λ”.
We shall write a cyclically ordered partition λ in the following ways:
 CYCLOPERMUTOHEDRON (TO NILOLAI DOLBILIN, WHO LOVES POLYTOPES) 5

(1) Sometimes we depict λ as a counterclockwise oriented circle with sub-

sets placed on the circle, as in Figure 2.
(2) Alternatively, we cut λ at any place and get a string of sets (I1 , I2 , ..., Ik ).
We keep in mind that
(I1 , I2 , ..., Ik ) = cycl(I1 , I2 , ..., Ik ) = (Ik , I1 , I2 , ..., Ik−1 ) =
= cycl2 (I1 , I2 , ..., Ik ) = (Ik−1 , Ik , I1 , I2 , ..., Ik−3, Ik−2 ), etc.
(3) For the vertices of CP n+1 , we use one more type of reduction. Given
a label λ of a vertex (that is, a cyclic ordering on [n + 1]), we write its
label as the linear ordering on [n], which is obtained from λ by cutting
through the entry (n + 1) and removing the entry (n + 1) from the
string. The obtained label we denote by λ.
For instance, the label
λ = ({3}, {4}, {1}, {5}, {6}, {2})
yields
λ = (2, 3, 4, 1, 5).
Conversely, given a linear ordering λ on the set [n], we cook a cycli-
cally ordered partitions of the set [n + 1] into (n + 1) singletons by
adding at the end the set {n + 1} and closing the string in a cycle.
For instance, (3, 2, 1) ∈ S3 yields ({3}, {2}, {1}), and then the cycli-
cally ordered partition
{3}
{2} {4}.
{1}
Proposition 1. For each n ≥ 3, the complex CP n+1 is defined correctly and
uniquely.
Proof. We construct the complex inductively. The 0-skeleton is obviously
well-defined. Assume that we have already the k-skeleton and that we wish to
attach a (k + 1)-cell C labeled by some cyclically ordered partition
(I1 , I2 , ..., In−k ) = (I2 , I3 , ..., In−k , I1 ) = (I3 , I4 , ..., I1 , I2 ) = ....
All the cells of the k-skeleton that should be incident to C form a subcomplex
of the k-skeleton which is combinatorially isomorphic to the boundary complex
of the Cartesian product of permutohedra
∂(Πn1 × ... × Πnn−k ),
where ni = |Ii |. Obviously, it is a k-dimensional sphere, and there is a unique
way to attach the boundary ∂C to the sphere. 
Corollary 1. Each closed cell of the complex CP n+1 is combinatorially equiv-
alent to a Cartesian product of permutohedra. 
6 GAIANE PANINA

Lemma 1. Let λ = (I1 , I2 , ..., Ik ) be the label of some cell of the complex
CP n+1 . We assume that the entry (n + 1) belongs to the set Ik .
The (labels of the) vertices of the cell λ can be retrieved via the following
algorithm:
(1) Take the string λ = (I1 , I2 , ..., Ik ) and remove the entry n + 1 from Ik .
(2) Take all possible orderings inside each of the sets Ij , j = 1, 2, ..., k, and
list all the resulting strings. We get some set V (λ).
(3) Apply cyclic permutations cycl0 , cycl1, cycl2 , ..., cycl|Ik |−1 to all the ele-
ments of V (λ). We get
V0 (λ) = V (λ), V1 (λ) := cycl1 V (λ), ..., V|Ik |−1 (λ) := cycl|Ik |−1 V (λ).
(4) The vertex set of the cell λ is the union of the sets:
[ [ [ [
V ert(λ) = V0 V1 V2 ... V|Ik |−1 . 
Example 2. For λ = ({1, 2}, {3}, {4, 5, 6}), we have

V ert(λ) =
{(1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (2, 1, 3, 5, 4), (2, 1, 3, 4, 5),
(5, 1, 2, 3, 4), (4, 1, 2, 3, 5), (4, 2, 1, 3, 5), (5, 2, 1, 3, 4),
(4, 5, 1, 2, 3, ), (5, 4, 1, 2, 3), (5, 4, 2, 1, 3), (4, 5, 2, 1, 3, )}. 
To give a reader more intuition, we complete the section by yet another
example.
{2} {5}

{1} {4}
{3}

{5} {2} {2} {4}

{2}{1}{3}{4}

{1} {4} {1} {5}

{3} {3}

{1}{3}{4}{2} {4}{2}{1}{3}

{3} {1}

{4,2,5}

{4} {2}
{1}{3}{2}{4}
{5} {2}{4}{1}{3}
{4} {5}
{1}

{4}{1}{3}{2} {3}
{1} {2}
{3}
{4} {5}

{1} {2}
{3}

Figure 3. The 2-face of the complex CP5 labeled by ({1}{3}{4, 2, 5})

 CYCLOPERMUTOHEDRON (TO NILOLAI DOLBILIN, WHO LOVES POLYTOPES) 7

Example 3. For n = 4, Figure 3 presents a hexagonal 2-face of the complex

CP5 and all the vertices of the face.

3. Cyclopermutohedron: realization as a virtual polytope

Assuming that {ei } are standard basic vectors in Rn , define the points
Pn
Ri = j=1 (ej − ei ) = (−1, ... −1, n − 1, −1, ... −1, −1, −1, ) ∈ Rn ,
i
and the following two families of line segments:
qij = [ei , ej ] , i<j
and
ri = [0, Ri ] .
We also need the point S = (1, 1, ..., 1) ∈ Rn .
Definition 1. The cyclopermutohedron is a virtual polytope defined as the
weighted Minkowski sum of line segments:
X n
X
CP n+1 := qij + S − ri .
i<j i=1

Clearly, CP n+1 lies in the hyperplane

n(n + 1)
x1 + ... + xn = ,
2
so its actual dimension is (n − 1).
Remark 1. The Minkowski sum
X
qij + S
i<j

is known to be equal to the standard permutohedron Πn (see [11]). Therefore

we can write
n
X
CP n+1 = Πn − ri .
i=1

Remark 2. The symmetric group Sn acts on the Rn by permuting the coor-

dinates. The action preserves the sets {qi,j } and {ri }, so both permutohedron
and cyclopermutohedron are invariant under the action. We shall refer to this
property as the symmerty property of the polytopes.
A curios and crucial feature of the cyclopermutohedron is the following:
8 GAIANE PANINA

Proposition 2. The set of vertices of CP n+1 equals the set of vertices of the
standard permutohedron Πn :
V ert(CP n+1 ) = V ert(Πn ). 

The proposition allows us to label the vertices of the cyclopermutohedron

by the labels borrowed from the permutohedron.
More detailed, each vertex v of CP n+1 is a vertex of Πn , and therefore, its
coordinates is some permutation on [n]. We label the vertex v by the inverse
permutation. For instance, the vertex with coordinates (4, 1, 5, 3, 2) is labeled
by λ = (2, 5, 4, 1, 3).
Next, remind that each label yields automatically a cyclic ordering on the
set [n + 1] by adding to λ the entry (n + 1) at the end and closing the label in
the circle.
Therefore we have:
Corollary 2. The vertices of CP n+1 are canonically labeled by (all possible)
cyclic orderings on the set [n + 1].
Definition 2. We define a bijection
ϕ : V ert(CPn+1 ) → V ert(CP n+1 )
between the vertex sets of the cell complex CPn and the cyclopermutohedron.
Given a vertex v ∈ V ert(CPn+1 ) labeled by λ, the bijection ϕ maps it to the
vertex of the CP n labeled by λ. By construction, it coincides with the vertex
of Πn labeled by λ.
Theorem 1. The bijection ϕ extends to a combinatorial isomorphism between
the complex CPn+1 and the cyclopermutohedron CP n+1 .
More precisely, the following holds:
(1) A subset V ⊂ V ert(CPn+1 ) is the vertex set of some cell of the complex
CPn+1 if and only if ϕ(V ) is the vertex set of some face of CP n+1 .
(2) The k-faces of CP n+1 can be labeled by (all possible) cyclically ordered
partitions of the set [n + 1] into (n − k + 1) non-empty parts.
(3) With this labeling, a face F ′ is a face of a face F if and only if the label
of F ′ refines the label of F .

Example 4. CP 4 is a two-dimensional virtual polytope, however, the defini-
tion puts in in R3 . Figure 4, left depicts the virtual polytope
X 3
X
qij − ri .
1≥i>j≥3 i=1

After the parallel translation by S = (1, 1, 1), we get the cyclopermutohedron

CP 4 (right). (A more detailed explanation of how to compute Minkowski
 CYCLOPERMUTOHEDRON (TO NILOLAI DOLBILIN, WHO LOVES POLYTOPES) 9

difference in the plane one finds in Section 6). In the figure, we indicate the
coordinates of the vertices. After replacing coordinates by labels, we arrive
exactly at the complex CP4 (compare with Figure 2).

213 123
102 012

3 312 132
201 021
1 2

321 231
210 120

Figure 4. Basis vectors in R3 , the polytope i<j qij − 3i=1 ri

P P

(left), and the cyclopermutohedron CP 4 with coordinates of the

vertices (right).

Example 5. The cyclopermutogedron CP 5 is a 3-dimensional virtual poly-

tope. Here is the complete list of its faces (see also Figure 5).
(1) By Proposition 2, the vertices of CP 5 are the vertices of the standard
permutohedron Π4 .
(2) The edges are of two types: those coinciding with the edges of the
standard permutohedron Π4 , and diagonal edges equal to the parallel
translates of the segments ri . The labels of the endpoints of a diagonal
edge differ by a cyclic permutation cycl.
For instance, the vertices (2, 1, 4, 3) and (1, 4, 3, 2) share a diagonal
edge which is a parallel translate of r2 = [0, (−1, 3, −1, −1)].
(3) The 2-faces fall into four categories (see Figure 5):
(a) Virtual hexagons of type (qij − ri − rj ). These are combinatorial
permutohedra Π3 .
(b) Convex quadrilaterals, faces of the standard permutohedron Π4 .
(c) Quadrilaterals of type qij × (−rk ), and
(d) Convex hexagons, faces of the standard permutohedron Π4 .
10 GAIANE PANINA

2314 2341
(a)
3214 3241

2431 3421
2134 3124

2143 2413 4231 4321

1234
1324 3142 4213 3412

1243 4312

1342 4123

1423 1432 4132

(b) ( c) (d)

Figure 5. There are four types of 2-faces of the cyclopermu-

tohedron CP 5 . We depict here representatives of all the types.
Their labels are: (a) ({1}{4}{2, 3, 5}), (b) ({1, 3}{4, 2}{5}),
(c) ({1, 3}{2}{4, 5}), (d) ({1, 2, 3}{4}{5}).

4. Cyclopermutohedron is the universal polytope for the

moduli spaces of planar polygonal linkages
A polygonal n-linkage is a sequence of positive numbers L = (l1 , . . . , ln ). It
should be interpreted as a collection of rigid bars of lengths li joined consecu-
tively in a chain by revolving joints.
We assume that L satisfies the triangle inequality.
A configuration of L in the Euclidean plane R2 is a sequence of points
R = (p1 , . . . , pn ), pi ∈ R2 with li = |pi , pi+1 |, and ln = |pn , p1 |.
The set M(L) of all configurations modulo orientation preserving isometries
of R2 is the moduli space, or the configuration space of the linkage L.
We assume that no configuration of L fits a straight line. This assumption
implies that the moduli space M(L) is a closed (n − 3)-dimensional manifold.

Definition 3. A partition of the set {l1 , . . . , ln } is called admissible if the

total length of any part does not exceed the total length of the rest.
 CYCLOPERMUTOHEDRON (TO NILOLAI DOLBILIN, WHO LOVES POLYTOPES) 11

In the terminology of paper [3], all parts of an admissible partition are short
sequences.
Instead of partitions of {l1 , . . . , ln } we shall speak of partitions of the set [n],
keeping in mind the lengths li .
It is proven (see [9]) that the moduli space M(L) admits a structure of
a regular cell complex (denoted by CW M ∗ (L)) whose description reads as
follows.
(1) The k-cell of the complex are labeled by (all possible) admissible cycli-
cally ordered partition of [n] into (n − k) non-empty subsets. Given a
cell C, its label is denoted by λ(C).
(2) A closed cell C belongs to the boundary of another closed cell C ′ when-
ever the label λ(C ′ ) is finer than the label λ(C).
In other words, the moduli space M(L) is patched of the admissibly labeled
cells of the complex CPn .
An immediate consequence of the construction is the following theorem:
Theorem 2. For any n-linkage L, the cell complex CW M ∗ (L) embeds as a
subcomplex in the face lattice of the cyclopermutohedron CP n . 

5. Proofs
Definition 7 says that given a virtual polytope K, its faces are associated to
non-zero vectors ξ. Thus, to list all the faces of the cyclopermutohedron, we
need to compute the face CP ξn+1 for each ξ.
So we fix a non-zero vector ξ = (x1 , x2 , ..., xn ), assuming by symmetry that
x1 ≥ x2 ≥ ... ≥ xn .
Next, we assume that the values xi appear in m clusters of equal entries, that
is,
x1 = x2 = ... = xi1 > xi1 +1 = xi1 +2 = ... = xi2 > xi2 +1 = xi2 +2 = ... etc.
Denote the clusters by Up , and denote their lengths by dp = ip+1 − ip :
U1 = {1, 2, ..., i1}, U2 = {i1 + 1, i1 + 2, ..., i2 }, etc.
We say that a vector ξ is diagonal-free if ξ is orthogonal to none of ri .
Otherwise we call ξ a diagonal vector.
We first make two elementary observations:
Lemma 2. Assume that ξ is a diagonal vector, which means that ξ is orthog-
onal to some rj . Then ξ is orthogonal to ri if and only if the indices j and i
belong to one and the same cluster. 
Lemma 3. If η is a small perturbation of ξ, then the cluster scheme related to
η refines the cluster scheme related to ξ. Moreover, given ξ, a suitable choice
of a small perturbation η, one gets any prescribed refinement. 
12 GAIANE PANINA

Since for virtual polytopes, ”face of the sum equals sum of the faces” (see
Proposition 4), we have:
n
!ξ n
ξ
X X X ξ X
CP n+1 = qij + S − ri = qij + S + (−ri )ξ .
i<j i=1 i<j i=1

So we first compute the faces of the summands. The latter are either points,
or (either convex or inverse to convex) line segments.

Faces of the summands.

Lemma 4. The face of the line segment qij is either its vertex ei , or the entire
segment:

ξ ei , if i and j belong to different clusters ;
qij =
qij , if i and j belong to one and the same cluster. 
Lemma 5. If ξ is diagonal-free, we have:
(1) Let k(ξ) = k ∈ N be such that
x1 + ... + xn
xk > > xk+1 .
n
Then the face of the line segment ri is the point:

Ri , if index i preceeds Uk , that is, i < ik−1 + 1;
riξ =
0, otherwise.
(2) By Proposition 4, for the Minkowski inverse −ri , we have

ξ −Ri , if index i preceeds Uk , that is, i < ik−1 + 1;
(−ri ) =
0, otherwise. 
Lemma 6. If ξ is a diagonal vector, then there is a uniquely defined cluster
Uk such that
x1 + ... + xn
∀i ∈ Uk , xi = .
n
Then we have:

 ri , if i ∈ Uk ;
ξ
ri = Ri , if index i preceeds Uk , that is, i < ik−1 + 1;
0, if index i comes after Uk , that is, i > ik .


and therefore,

 −ri , if i ∈ Uk ;
ξ
(−ri ) = −Ri , if index i preceeds Uk , that is, i < ik−1 + 1;
0, if index i comes after Uk , that is, i > ik . 

 CYCLOPERMUTOHEDRON (TO NILOLAI DOLBILIN, WHO LOVES POLYTOPES) 13

Proof of Proposition 2. Assume that ξ = (x1 , ..., xn ) ∈ Rn is a diagonal-free

vector such that x1 > ... > xn (that is, all the clusters are singletons).
Assume also that the index k satisfies
x1 + ... + xn
xk > > xk+1 .
n
Prove that the face
n
X n
X
CP ξn+1 = (Πn − ri )ξ = Πξn − (ri )ξ
i=1 i=1

is a one-point polytope that coincides with some vertex of Πn . (n, The face of
the permutohedron is the vertex
Πξn = (n − 1, n − 2, ..., 2, 1).
By Lemmata 5 and 4, in this particular case all the faces are also points,
therefore it remains to sum them up. We have n − k + 1 summands:
(n, n − 1, n − 2, ... 2, 1)
+(1 − n, 1 1 ... 1, 1)
+(1, 1 − n, 1 ... 1, 1)
+(1, 1, 1 − n, ... 1, 1)
The sum equals
((n − k), (n − k − 1), (n − k − 2), ..., 3, 2, 1, n, (n − 1), ..., (n − k + 1)) ∈ V ert(Πn )
which is a vertex of the standard permutohedron. By the symmetry property,
each of the vertices of Πn arises in this way.
Note that in the framework of the proof, we dealt with the coordinates of
the vertices, not with the labels. We remind that the label is the inverse
permutation. In particular, the vertex we discussed is labeled by

(k, (k − 1), (k − 2), ..., 3, 2, 1, n, (n − 1), ..., (k + 1)). 

Proof of Theorem 1. Basing on Lemmata 4 , 5, and 6, we put labels on the

faces of the cyclopermutohedron. By symmetry property, it suffices to assume
that
x1 ≥ x2 ≥ ... ≥ xn .
Before we start putting labels, observe that the face CP ξn+1 depends only on
the following three conditions: (1) whether ξ is diagonal or not, (2) the cluster
scheme, and (3) the number k = k(ξ) defined in Lemmata 5 and 6.
14 GAIANE PANINA

Putting labels on diagonal-free faces of CP n+1 . For a diagonal-free vector

ξ, we say that CP ξn+1 is a non-diagonal face, and label the face as follows:
(1) Start with the label (U1 , U2 , ..., Um ), where Ui are the clusters associated
with the vector ξ. We have a linearly ordered partition of [n].
(2) Add the one-element set {n + 1} right after Uk−1 , and close the string
in a circle. We get the label
(U1 , U2 , ..., Uk−1 , {n + 1}, Uk , Uk+1 , ..., , Um ) =
= ((Uk , Uk+1 , ..., , Um , U1 , U2 , ..., Uk−1 , {n + 1}),
which should be interpreted as a cyclically ordered partition of [n + 1].
Putting labels on diagonal faces of CP n+1 . For a diagonal vector ξ, we
say that CP ξn+1 is a diagonal face, and label the face as follows:
(1) Start with the label (U1 , U2 , ..., Um ), where Ui are the clusters associated
with the vector ξ.
(2) Add the entry (n + 1) in the set Uk , and close the string in a circle.
We get the label
(U1 , U2 , ..., Uk−1 , {(n + 1)} ∪ Uk , Uk+1 , ..., , Um ),
which should be interpreted as a cyclically ordered partition of [n + 1].
The following lemmata follow more or less directly from the construction,
and complete the proof of Theorem 1.
Lemma 7. Let a vector η be a small perturbation of ξ. Then the label of
CP ηn+1 refines the label of CP ξn+1 . 
Lemma 8. Two vectors ξ and ξ ′ generate one and the same cyclic label if and
′
only if the faces CP ξn+1 and CP ξn+1 coincide.
Proof. By the label, one easily distinguishes whether ξ is diagonal or not.
As we know from above, each face equals weighted sum of (some of) the seg-
ments qij and ri . Which ones should be taken, is understood from the cluster
structure. This means that the faces with equal labels differ by translation. To
prove that they are equal, it remains to observe that equal labels yield equal
vertex sets. 
Lemma 9. Let λ be the label of a face F , and λ′ be its refinement. There
exist a vector ξ and its small perturbation η such that F = CP ξn+1 , and λ′ is
the the label of CP ηn+1 . 
 CYCLOPERMUTOHEDRON (TO NILOLAI DOLBILIN, WHO LOVES POLYTOPES) 15

6. Virtual polytopes
Virtual polytopes appeared in the literature as useful geometrization of
Minkowski differences of convex polytopes. A detailed discussion can be found
in [5, 6, 7].

Virtual polytopes: definitions. A convex polytope is the convex hull of a

finite, non-empty point set in the Euclidean space Rn . Degenerate polytopes
are also included, so a closed segment and a point are polytopes, but not the
empty set. We denote by P + the set of all convex polytopes.
Definition 4. Let K and L ∈ P + be two convex polytopes. Their Minkowski
sum K + L is defined by:
K + L = {x + y : x ∈ K, y ∈ L}.
Minkowski addition the set P + to a commutative semigroup whose unit
element is the convex set containing exactly one point E = {0}.
Definition 5. The group P of virtual polytopes is the Grothendick group
associated to the semigroup P + of convex polytopes under Minkowski addition.
The elements of P are called virtual polytopes.
More instructively, P can be explained as follows.
(1) A virtual polytope is a formal difference K − L.
(2) Two such expressions K1 − L1 and K2 − L2 are identified, whenever
K1 + L2 = K2 + L1 .
(3) The group operation is defined by
(K1 − L1 ) + (K2 − L2 ) := (K1 + K2 ) − (L1 + L2 ).

L’ L
K

K-L

Figure 6. Minkowski difference of two polygons

16 GAIANE PANINA

- =

Figure 7. Minkowski difference of the polygons

X 3
X
qij and ri .
1≥i>j≥3 i=1

Algorithm 1. In R2 , virtual polytopes can be visualized as closed polygonal

chains according a simple algorithm. For polygons with mutually non-parallel
edges (this is what we have in the definition of cyclopermutohedron), it runs
as follows.
(1) To compute K − L, orient the polygons K and the symmetric image
L′ of L clockwise and counterclockwise respectively.
(2) Take the (oriented) edges of K and L′ apart and order them by the
slope.
(3) Following the ordering, compose a closed polygonal chain, as is shown
in Figure 6.
Example 6. For the particular case of Example 4, the algorithm gives us
Figure 7. Observe that if we generically perturb one of the summands, the
sum would have (instead of six) twelve vertices.
Faces of virtual polytopes. Similar to convex polytopes, the virtual poly-
topes also have well defined faces together with incidence relations.
To explain it,we first define in an appropriate way faces of convex polytopes.
Definition 6. Let K ⊂ Rn be a convex polytope, and ξ be a vector in Rn .
The polytope K ξ is the subset of K where the scalar product (·, ξ) attains its
maximal value:
K ξ = {x ∈ K| ∀y ∈ K, (x, ξ) ≥ (y, ξ)}.
K ξ is called the face of K with the normal vector ξ, or the face of K in direction
ξ. If ξ is a non-zero vector, we get a proper face of the polytope.
Proposition 3. (1) A face of a convex polytope is a convex polytope.
(2) A face of a face of K is again a face of K.
(3) A face in the direction ξ of a Minkowski sum of two convex polytopes
is the Minkowski sum of the faces in direction ξ from the summands:
(K + L)ξ = K ξ + Lξ .
The item (3) of the above proposition motivates us to define faces for virtual
polytopes:
 CYCLOPERMUTOHEDRON (TO NILOLAI DOLBILIN, WHO LOVES POLYTOPES) 17

Definition 7. Given a virtual polytope K = L − M ∈ P, where K and L are

convex polytopes, and ξ ∈ Rn , the face K ξ is defined by
K ξ = (L − M)ξ := Lξ − M ξ .
As in the convex case, we rank the faces by their dimensions. The k-
dimensional faces are called k-faces; the 0-faces and the 1-faces are called
vertices and edges respectively.
The faces of virtual polytopes satisfy properties similar to the convex case:
Proposition 4. [6]
(1) A face of a virtual polytope is a virtual polytope.
(2) A face of a face of a virtual polytope K is again a face of K.
(3) ”Face of the sum is sum of faces”.
(K + L)ξ = K ξ + Lξ , and (−K)ξ = −(K ξ ). 
Proposition 5. For a virtual polytope K and its face F , the faces of F can
be obtained in the following way.
(1) Take all possible ξ such that F = K ξ .
(2) Perturb ξ, that is, take all vectors η that are sufficiently close to ξ.
(3) For all those η, take K η . All the resulted virtual polytopes give the set
of faces of F .
Proof. The statement is true for convex polytopes and extends by linearity
to virtual polytopes as well. 
References
[1] F. Chapoton, S. Fomin and A. Zelevinsky, Polytopal Realizations of generalized associa-
hedra, Canad. Math. Bull. 45 (2003), 537–566.
[2] I.Gelfand, M. Kapranov, A. Zelevinskii, Discriminants, Resultants and Multidimensional
Determinants, Birkhauser, Boston, 1994.
[3] M. Farber and D. Schütz, Homology of planar polygon spaces, Geom. Dedicata, 125
(2007), 75-92.
[4] M. Kapranov, The permutoassociahedron, Mac Lane’s coherence theorem and asymptotic
zones for the KZ equation, Journal of Pure and Applied Algebra, Vol. 85, 2 (1993),
119–142.
[5] A. Khovanskii and A. Pukhlikov, Finitely additive measures of virtual polytopes, St.
Petersburg Math. J., Vol. 4, 2 (1993), 337-356.
[6] G. Panina, Virtual polytopes and some classical problems, St. Petersburg Math. J., Vol.
14, 5 (2003), 823–834.
[7] G. Panina, New counterexamples to A.D. Alexandrov’s uniqueness hypothesis, Advances
in Geometry, Vol. 5, 2 (2005), 301-317.
[8] G. Panina, Arifmetika mnogogrannikov (in Russian), Kvant, Vol. 4, (2010), 8-13.
http://www.kvant.info/k/2009/4/01-10.pdf
[9] G. Panina, Moduli space of a planar polygonal linkage: a combinatorial description,
arXiv:1209.3241
[10] A. Postnikov,Permutohedra, Associahedra, and Beyond, Int Math Res Notices Vol. 2009
(2009), 1026-1106.
18 GAIANE PANINA

[11] G.M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics. (Springer, Berlin
1995).

* † Institute for Informatics and Automation, St. Petersburg, Russia,

Saint-Petersburg State University, St. Petersburg, Russia, e-mail:gaiane-
[email protected].