Seminar

A triangulation of the $n$-gon can be understood as a maximal crossing-free set of diagonals, and a subdivision as any crossing-free set of diagonals. By a ``diagonal’’, we mean an element of $\binom{[n]}{2} \setminus \{ \{i,i+1\} : i \in [n]\}$. Since every triangulation consists of $n-3$ diagonals, subdivisions form a pure simplicial complex of dimension $n-4$, whose facets are the triangulations. This complex is called the (polar) associahedron and it is polytopal. That is, it is isomorphic to the complex of proper faces of a simplicial $(n-3)$-polytope, the dual of the associahedron.

The above can be generalized as follows: call a $k$-crossing a set of diagonals $\{a_1,b_1\},\dots, \{a_k,b_k\}$ with $a_1 < a_2 < \dots a_k < b_1 < \dots < b_k\}$ and define a $k$-multitriangulation as a maximal set of $k$-crossing-free diagonals. This defines a simplicial complex one the set of ``diagonals of length at least $k+1$’’, that is, on the set $\{ \{a,b\} \in \binom{[n]}{2} : k < |a - b| < n-k \}$. This defines a simplicial complex that we call the $(n,k)$-multiassociahedron. The complex is known to be pure of dimension $k(n-2k-1)-1$ [Capoyleas and Pach], and it is also known to be a shellable sphere [Jonsonn]. It is natural to conjecture that this sphere is polytopal, that is, it can be realized as the boundary complex of a polytope of dimension $k(n-2k-1)$ … but finding such a realization has proven to be a difficult task. This is surprising, since the associahedron itself admits to be realized in different manners:

- As a secondary polytope; that is, using as coordinates the areas of the triangles of a triangulation, in the manner prescribed by Gel’fand, Kapranov and Zelevinskii. For $k$-multitriangulations, their description as ``complexes of star $(2k+1)$-polygons by Pilaud and Santos produces a natural way of defining a vector with $k$ ``areas’’ per point.

- As a ``polytope of expansive motions’’, as introduced by Rote-Santos-Streinu. This construction is based on the fact that a triangulation is an isostatic graph in dimension two, meaning that it is generically rigid but deleting any single edge makes it generically flexible. For $k$-triangulations, the number $k(n-2k-1)$ of diagonals in them is exactly the number needed for isostatic graphs on $n$ vertices in dimension $2k$. For $k=2$ it is proven that they are indeed isostatic, but for higher $k$ this is only conjectured.

- As the ``brick polytope’’ associated to a sorting network. Brick polytopes (introduced by Pilaud-Santos) are a way to realize some ``sub word complexes’’ in the root system of type A (they were generalized to other types by Pilaud and Stump). Under certain conditions they can be proved to be polytopal, but in general they are only conjectured to be so. In fact, multiassociahedra are ``universal’’ among sub word complexes of type A, meaning that if they are polytopal then every sub word complex is.

In this talk I will review these, and perhaps other, failed attempts at realizing multiassociahedra; most of this is joint work with Vincent Pilaud.