2014/01/29 by Gaiane Panina, Panina, Gaiane
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Point processes and geometric inequalities #math.CO #math.MG #msc:52B05 #msc:52B11 #msc:52B70
paper · pdf · doi:10.48550/arxiv.1401.7476
arxiv created 2014/11/09 · arxiv updated 2014/11/11
It is known that the k-faces of the permutohedron Πn are 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 defined in analogous way, replacing linear ordering by cyclic ordering. Namely, k-cells of the complex CP 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 again corresponds to the refinement: a cell F contains a cell F' whenever the label of F' refines the label of F. In particular, two vertices are joined by an edge whenever their labels differ on a permutation of two neighbor elements. The complex CP 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 (Minkowski difference of two convex polytopes) which we call "cyclopermutohedron" CPn+1. It is defined explicitly, as a weighted Minkowski sum of line segments. Informally, 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.