It is well known that the $k$-faces of the permutohedron $\Pi_n$ can be labeled by (all possible) linearly ordered partitions of the set $[n]=\{1,\dots,n\}$ into $n-k$ nonempty 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$. We consider the cell complex $\mathrm{CP}_{n+1}$ defined in a similar way but with the linear ordering replaced by the cyclic ordering. Namely, the $k$-cells of the complex $\mathrm{CP}_{n+1}$ are labeled by (all possible) cyclically ordered partitions of the set $[n+1]=\{1,\dots,n+1\}$ into $n+1-k>2$ nonempty parts. The incidence relation in $\mathrm{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 $\mathrm{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, the Minkowski difference of two convex polytopes), which we call a cyclopermutohedron $\mathcal{CP}_{n+1}$. It is defined explicitly as a weighted Minkowski sum of line segments. Informally, the cyclopermutohedron can be viewed as a “permutohedron with diagonals.” One of the motivations for introducing such an object is that the cyclopermutohedron is a “universal” polytope for moduli spaces of polygonal linkages.
