A polygonal $ n$ -linkage is a sequence of positive numbers $ L=(l_1,\dots ,l_n)$. It should be interpreted as a collection of rigid bars of lengths $ l_i$ joined consecutively in a chain by revolving joints. We always assume that the triangle inequality holds, that is, \begin{eqnarray*} \forall j, \ \ \ l_j< \frac{1}{2}\sum_{i=1}^n l_i \end{eqnarray*} which guarantees that the chain of bars can close. A planar configuration of $ L$ is a sequence of points \begin{eqnarray*} P=(p_1,\dots,p_{n}), \ p_i \in \mathbb{R}^2 \end{eqnarray*} with $ l_i=|p_i,p_{i+1}|$, and $ l_n=|p_n,p_{1}|$. We also call $ P$ a polygon .

As follows from the definition, a configuration may have self-intersections and/or self-overlappings.

The (second) definition shows that $ M(L)$ does not depend on the ordering of $ \{l_1,\ldots,l_n\}$; however, it does depend on the values of $ l_i$.

Throughout the paper (except for the Sect. 4) 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 (see [Farber2008]).

The manifold $ M(L)$ is already well studied, see [Farber2008], [Farber and Schütz2007],[Kapovich and Millson1995], and many other papers. Explicit descriptions of $ M(L)$ exist for $ n=4, 5, {\rm and}\, 6$, see [Farber2008],[Kapovich and Millson1995],[Zvonkine1997]. There also exist various results for polygonal linkages in 3D, see [Klyachko1994] for example.

The paper is organized as follows. Section 2 presents an explicit combinatorial description of $ M(L)$ as a regular cell complex $ \mathcal{K}(L)$. In a sense, the starting point of our approach is an elementary version of Gelfand–Goresky–MacPherson–Serganova idea from [Gelfand et al.1987]: they classify the planes (that is, the elements of Grassmanian) by some associated combinatorics. The equivalence classes of the planes form strata which may have complicated topology. In this paper we also classify configurations by their combinatorial types, but here we are lucky with that all equivalence classes are topological balls that patch together in a regular cell complex. The combinatorics of $ \mathcal{K}(L)$ is very much related (but not equal) to the combinatorics of the permutohedron. In Sect. 2 we present a number of examples and give a complete characterization of the possible combinatorics of cells.

In Sect. 3 we study the dual complex $ \mathcal{K}^*$ which comes almost automatically with a geometrical realization in the Euclidean space. The realization is related to cyclopermutohedron [Panina2015], which is a polytope that encodes cyclically ordered partitions of a finite set in the same way as the permutohedron encodes linearly ordered partitions.

Section 4 sketches the main result of [Galashin and Panina2016]: under a proper setting, a "polygonal linkage" can be replaced by a "simple game" (in the game-theoretic sense). A simple game cannot be interpreted as a physical object (like bar-and-joint mechanism) and therefore has no "configurations". However, it is possible to associate with it a cell complex which is proven to be a combinatorial manifold.

Finally, for the sake of completeness, we discuss in Sect. 4 the cell complex for the case when the manifold $ M(L)$ is singular.

The complex $ \mathcal{K}(L)$ already appeared in [Kapovich and Millson1995] in a slight disguise, where it was mentioned as a "tiling of $ M(L)$". Moreover, based on the Deligne-Mostow map, Kapovich and Millson deduced that $ \mathcal{K}(L)$ can be realized as a piecewise linear manifold in the hyperbolic space.

We start with necessary preliminaries. Convex configurations A configuration $ P$ is convex if (1) it is a convex (piecewise linear) curve, (2) no two consecutive edges are collinear, and (3) the orientation induced by the numbering goes counterclockwise.

The set of all convex configurations we denote by $ M_{conv}(L)$. The set $ \overline{M}_{conv}(L)$ is the closure of $ M_{conv}(L)$ in $ M(L)$.

Proof.

The permutohedron $ \Pi_n$ (see [Ziegler1995]) is defined as the convex hull of all points in $ \mathbb{R}^n$ that are obtained by permuting the coordinates of the point $ (1,2,\ldots,n)$. It has the following properties:

1. (1) $ \Pi_n$ is an $ (n-1)$-dimensional polytope.
2. (2) The $ k$-dimensional faces of $ \Pi_n$ are labeled by ordered partitions of the set $ \{1,2,\ldots,n\}$ into $ (n-k)$ non-empty parts. In particular, the vertices are labeled by the elements of the symmetry group $ S_n$. The label of a vertex is obtained by inverting the permutation of the coordinates of the vertex.
3. (3) A face $ F'$ of $ \Pi_n$ is contained in a face $ F$ iff the label of $ F'$ is finer than the label of $ F$. Here by a refinement of an ordered partition $ \lambda$ we mean an ordered refinement $ \lambda'$ whose ordering is inherited from $ \lambda$. For instance, $ \{1,3\}\{2,4\}\{5\}$ refines $ \{1,3\}\{2,4,5\}$ and does not refine $ \{2,4,5\}\{1,3\}$.
4. (4) A face of $ \Pi_n$ is the Cartesian product of permutohedra of smaller dimensions.
5. (5) The permutohedron is a zonotope , that is, the Minkowski sum of line segments.
6. (6) The permutohedra $ \Pi_1$, $ \Pi_2$, and $ \Pi_3$ are a one-point polytope, a segment, and a regular hexagon, respectively. The permutohedron $ \Pi_4$ (with its vertices labeled) is depicted in Fig. 1.

Figure 1 Permutohedron $ \Pi_4$.

The cyclic polytope $ C(d,n)$ is the convex hull of $ n$ distinct points $ x_1,\ldots,x_n$ on the moment curve in $ \mathbb{R}^d$, see [Ziegler1995]. Its combinatorics is completely defined by the following property ( Gale evenness condition ): a $ d$-subset $ F \subset \{x_1,\ldots,x_n\}$ forms a facet of $ C(d,n)$ iff any two elements of $ \{x_1,\ldots,x_n\} {\setminus} F$ are separated by an even number of elements from $ F$ in the sequence $ x_1,\ldots,x_n$.

Assume first that a configuration $ P=(p_1,\ldots,p_n)\in M(L)$ has no parallel edges, that is, no edgevectors $ \overrightarrow{p_ip}_{i+1}$ and $ \overrightarrow{p_jp}_{j+1}$ are parallel and codirected.

Then there exists a unique convex polygon $ \overline{P}$ such that

1. (1) The edges of $ P$ are in one-to-one correspondence with the edges of $ \overline{P}$. The bijection preserves the directions of the vectors.
2. (2) The orientations of the edges of $ \overline{P}$ give the counterclockwise orientation of $ \overline{P}$.

In other words, the edges of $ \overline{P}$ are the edges of $ P$ coming in the order of their slopes (see Fig. 2). Obviously, $ \overline{P} \in M_{conv}(\lambda L)$ for some permutation $ \lambda \in S_n$. The permutation is defined up to the action of the group generated by the cyclic permutation $ (2,3,4,\ldots,n,1)$. The orbit of a permutation under the action of the group is a cyclic ordering on the set $ [n]$. Summarizing the above, our construction assigns to $ P$ the label $ \lambda(P)$ which is a cyclic ordering on the set $ [n]$. Equivalently, expecting further discussion on polygons with parallel edges, we state that a label of a configuration without parallel edges is a cyclically ordered partition of the set $ [n]=\{1,2,\ldots,n\}$ into $ n$ non-empty parts.

Proof.

Figure 2 Labeling of a polygon with no parallel edges.

Figure 3 Labeling of a polygon with parallel edges.

Assume now that a configuration $ P\in M(L)$ has parallel edges. A permutation which makes $ P$ convex is not unique. Indeed, one can choose any ordering on the set of parallel edges. So in cooking the label, our construction puts the indices of parallel edges in one set.

The label $ \lambda(P)$ assigned to $ P$ is a cyclically ordered partition of the set $ [n]$, see Fig. 3 for an example.

Proof.

We stress once again that the order of the sets matters, whereas there is no ordering inside a set. For example, \begin{eqnarray*} (\{1\} \{3 \} \{4, 2, 5,6\})\neq(\{3 \}\{1\} \{4, 2, 5,6\})= ( \{3 \}\{1\}\{ 2,4, 5,6\}). \end{eqnarray*}

Before we formulate the main theorem, remind that a CW-complex can be constructed inductively by defining its skeleta. Once the $ (k - 1)$-skeleton is constructed, we attach a collection of closed $ k$-balls $ C_i$ by some continuous mappings $ \varphi_i$ from their boundaries $ \partial C_i$ to the $ (k-1)$-skeleton. For a regular complex, each of the mappings $ \varphi_i$ is injective, and $ \varphi_i$ maps $ \partial C_i$ to a subcomplex of the $ (k-1)$-skeleton, see [Hatcher2002]. Regularity of a complex implies that a complex is uniquely defined by the poset of its cells. Regularity also guarantees the existence of well-defined barycentric subdivision and (for PL manifolds) a well-defined dual complex.

Proof.

For the complex $ \mathcal{K}(L)$ we immediately have:

Proof.

Figure 4 $ \mathcal{K}(L)$ for the 4-gonal linkage $ (1,1,1,1/2)$ .

Proof.

In a regular complex, the boundary of each cell is a combinatorial sphere, so it makes sense to speak of combinatorics of a cell. Let us look what types of combinatorics do we encounter in complexes $ \mathcal{K}(L)$ for different linkages $ L$.

Proof.

Proof.

Proof.

We describe below a realization of $ \mathcal{K}^*$ in the Euclidean space $ \mathbb{R}^{n-2}$. For this, we need a preliminary construction which is the subject of paper [Panina2015]. The construction involves the theory of virtual polytopes developed originally in [Pukhlikov and Khovanskii1993], and some related technique. For the very first orientation we recommend the reader just to trust that there exists a well-defined Minkowski subtraction of convex polytopes, and that Minkowski differences have a well-defined facial structure. For more details, we refer to the above mentioned paper. Cyclopermutohedron For a fixed number $ n\geq3$, we define the following regular cell complex $ {CP}_{n}$ by listing all the closed cells together with the incidence relations.

• For $ k=0,\ldots,n-3$, the $ k$-dimensional cells ($ k$-cells, for short) of the complex $ {CP}_{n}$ are labeled by (all possible) cyclically ordered partitions of the set $ [n]$ into $ (n-k)$ non-empty parts.
• A (closed) cell $ F$ contains a cell $ F'$ whenever the label of $ F'$ refines the label of $ F$.

The complex $ {CP}_{n}$ 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 which we call cyclopermutohedron $ \mathcal{CP}_{n}$.

Here is the construction of cyclopermutohedron:

Assuming that $ \{e_i\}$ are standard basic vectors in $ \mathbb{R}^{n-1}$, define the points \begin{eqnarray*} \begin{array}{ccccccccc} R_i=\sum_{j=1}^{n-1} (e_j-e_i)=(-1, & \ldots & -1, & n-2, & -1, & \ldots & -1, & -1, &-1, )\in \mathbb{R}^{n-1},\\ & & & \ i & & & & & \end{array} \end{eqnarray*} and the following two families of line segments: \begin{eqnarray*} q_{ij}=\left[e_i,e_j\right], \ \ \ i< j \end{eqnarray*} and \begin{eqnarray*} r_i=\left[0,R_{i} \right]. \end{eqnarray*} We also need the point $ S=\left(1,1,\ldots,1\right)\in \mathbb{R}^{n-1}$.

In an oversimplified way, the cyclopermutohedron $ \mathcal{CP}_{n}$ can be visualized as the permutohedron $ \Pi_{n-1}$ "with diagonals". This means that all the proper faces of $ \Pi_{n-1}$ are also faces of $ \mathcal{CP}_{n}$. However, $ \mathcal{CP}_{n}$ has some extra faces in comparison with $ \Pi_{n-1}$.

For any $ n$-linkage $ L$, the complex $ \mathcal{K}^*(L)$ automatically embeds in $ {CP}_{n}$, and therefore embeds in the face complex of $ \mathcal{CP}_{n}$. The embedding goes as follows. Take the permutohedron $ \Pi_{n-1}\subset \mathbb{R}^{n-1}$, assuming (as usual) that the faces of $ \Pi_{n-1}$ are labeled by ordered partitions on the set $ [n-1]$. In particular, the vertices of $ \Pi_{n-1}$ are labeled by permutations of the set $ [n-1]$. We introduce the following bijection between the vertex sets \begin{eqnarray*} \psi: Vert(\mathcal{K}^*)\rightarrow Vert(\Pi_{n-1}). \end{eqnarray*} Given a vertex of $ \mathcal{K}^*$ whose label $ \lambda$ is a cyclically ordered set $ [n]$, the mapping $ \psi$ sends it to the vertex of $ \Pi_{n-1}$ by cutting $ \lambda$ at the position of "$ \{n\}$" and omitting "$ \{n\}$" from the label.

Thus, the vertices of $ \mathcal{K}^*$ are geometrically realized by vertices of the permutohedron. Next, we realize the cells of the complex: take a cell $ C$ and patch the face of the cyclopermutohedron which corresponds to $ C$ by Theorem 3.3.

This construction can be reformulated as the following surgery algorithm:

1. (1) Start with the complex $ \mathcal{K}^*(L)$ and the boundary complex of the permutohedron $ \Pi_{n-1}$. Realize the vertices of $ \mathcal{K}^*$ as the vertices of $ \Pi_{n-1}$ via the above described mapping $ \psi$.
2. (2) For every face $ F$ of $ \Pi_{n-1}$ do the following. The face is labeled by some $ \lambda$, which is a linearly ordered partition of $ \{1,\ldots,n-1\}$. If the partition is admissible (that is, all the parts are short), keep the face $ F$ and assign to it the label $ (\lambda, \{n\})$. If the partition is not admissible, remove the face $ F$ from the complex. This step gives a realization of all the cells of $ \mathcal{K}^*$ whose label contains the one-element set $ \{n\}$.
3. (3) Take all the cells $ C$ of $ \mathcal{K}^*$ such that the part of $ \lambda(C)$ containing $ n$ has more than one element. Patch in the corresponding face of the cyclopermutohedron, which up to a translation equals \begin{eqnarray*} \sum q_{ij} - \sum r_i, \end{eqnarray*} where the first (Minkowski) sum extends over all $ i< j< n$ such that $ i$ and $ j$ belong to one and the same part of the partition $ \lambda(C)$, and the second sum extends over all $ i< n$ such that $ i$ and $ n$ belong to one and the same part of the partition $ \lambda(C)$. This is a virtual polytope with the vertex set $ \psi (Vert(C))$.

Figure 5 The complex $ \mathcal{K}^*(L)$ for the $ 5$-linkage $ L=(1,2;\ 1;\ 1;\ 0,8;\ 2,2)$. We remove from the permutohedron the grey facets and patch in the blue cylinder .

Figure 6 A "diagonal" face .

For more examples of the surgery see [Gorodetskaya2017], where Gorodetskaya presented the surgery for all types of five-linkages.

The construction of $ \mathcal{K}$ and $ \mathcal{K}^*$ suggests some further natural discussions sketched briefly in this section. Quasilinkages, Simple Games, Alexander Self-Dual Complexes, and Associated Manifolds An elementary observation is that the complex $ \mathcal{K}(L)$ depends only on the collection of admissible partitions. In turn, these are defined by the collection of short sets. This suggests the following generalization, which is described in details in [Galashin and Panina2016], and which we sketch very briefly now.

The proposed notion exists in the literature; yet in completely different frameworks. It appeared as "simple game with constant sum" in game theory, as "strongly complementary simplicial complex", and as "Alexander self-dual simplicial complex".

Being motivated by polygonal linkages, we call any $ S\in \mathcal{F}$ a short set , and any $ S\notin \mathcal{F}$ a long set .

Each polygonal linkage $ L$ yields a collection of short sets, and therefore, is a quasilinkage. The converse is not true: there exist many quasilinkages that cannot be represented by length assignments.

We associate with a quasilinkage $ \mathcal{F}$ a cell complex $ \mathcal{K}(\mathcal{F})$ by applying the rules from Theorem 2.6. In [Galashin and Panina2016] it is proven that the complex is a (combinatorial) manifold of dimension $ (n-3)$ which is locally isomorphic to $ \mathcal{K}(L)$ for some linkage $ L$ (however, $ L$ depends on the location, and there may be no linkage associated to the entire complex). Cell Decomposition for Singular Configuration Spaces A similar cell complex exists also for singular configuration spaces, that is, for the case when $ L$ has configurations that fit in a straight line.

The combinatorics of the complex $ \mathcal{K}(L)$ is literally the same as in Theorem 2.6 except for the following items:

1. (1) Non-singular vertices are labeled by admissible partitions with exactly three parts.
2. (2) Singular vertices are labeled by admissible partitions with exactly two parts.
3. (3) Assume that a singular vertex $ v$ of $ \mathcal{K}(L)$ corresponds to an ordered partition of $ \{1,2,\ldots,n\}$ into two non-empty parts, say, with $ k$ and $ l$ elements. Then the vertex figure of $ v$ is combinatorially equivalent to the cone over $ (\partial \Pi_k\times \partial \Pi_l)^* $.