# Triangulations of cyclic polytopes

Steffen Oppermann<fnref n="1" /> and Hugh Thomas<fnref n="2" />

**Abstract.** We give a new description of the combinatorics of triangulations of even-dimensional cyclic polytopes, and of their bistellar flips. We show that the tropical exchange relation governing the number of intersections between diagonals of a polygon and a lamination (which generalizes to arbitrary surfaces) can also be generalized in a different way, to the setting of higher dimensional cyclic polytopes.

**Résumé.** Nous donnons une nouvelle déscription de la combinatoire des triangulations des polytopes cycliques, et de leurs mouvements bistellaires. Nous démontrons que la relation d'échange qui gouverne le nombre d'intersections entre les diagonaux d'une polygone et une lamination (qui peut être généralisée à une surface arbitraire) peut également être généralisée au cadre des polytopes cycliques.

**Keywords:** cyclic polytopes, triangulation, bistellar flip, cluster algebra, tropical arithmetic

## 1 Introduction

By a triangulation of a (convex) $m$-gon, we mean a subdivision of the $m$-gon into triangles, by adding diagonals which do not cross in the interior of the $m$-gon. There is a natural graph structure on the set of triangulations of an $m$-gon: two triangulations are adjacent iff they are related by a single *diagonal flip* in which a diagonal is removed, and replaced by the other diagonal of the quadrilateral which results.

Let $P$ be a set of points in $\mathbb{R}^e$. For simplicity, and because it is all we will need, we assume that the points of $P$ are in general position, i.e., with no more than two on any line, three in any (affine) plane, and so forth. A triangulation of $P$ is defined to be a decomposition of the convex hull of $P$ into $e$-dimensional simplices whose vertices are points of $P$. There is a graph structure on triangulations in this generality. Given any $e+2$ points in $\mathbb{R}^e$ (which, by our assumption of general position, do not all lie in a hyperplane), there are two ways to triangulate their convex hull. We say that two triangulations $S$ and $T$ of $P$ are related by a *bistellar flip* if there are some $e+2$ points of $P$ such that $S$ and $T$ coincide outside the convex hull of these points, and restricted to the convex hull of these points, $S$ and $T$ agree with the two different triangulations of these points. Two triangulations are then considered to be adjacent in the graph structure iff they are related by a bistellar flip. For more details on triangulations and bistellar flips, and greater generality, see [DRS].

In the case of triangulations of an $m$-gon, we have the following trivial observations:

1. A triangulation is uniquely determined by the collection of $m-3$ diagonals appearing in it.

2. Any collection of $m-3$ non-crossing diagonals defines a triangulation.

<footnote n="1">¹Institutt for matematiske fag, NTNU, 7491 Trondheim, Norway</footnote>

<footnote n="2">²Department of Mathematics and Statistics, University of New Brunswick, Fredericton NB, E3B 1J4 Canada</footnote>
3. Triangulations $S$ and $T$ are related by a flip iff $S$ and $T$ have exactly $m-4$ diagonals in common.

It is natural to ask whether this kind of description of triangulations can be generalized. Indeed, there is one generalization which is now well-known, in which we remove the convexity, and replace diagonals by isotopy classes of curves in an arbitrary surface, with marked points on its boundary components where the curves are required to begin and end, and then consider the set of triangulations that arises in this way. This approach is used to define the cluster algebra associated to such a surface (provided the surface is orientable). The arcs correspond to cluster variables, and the diagonal flip corresponds to the mutation of cluster variables.

In this abstract, we consider a different kind of generalization, in which we remain in the world of convexity, but we increase the dimension of our space. Specifically, we consider the triangulations of even-dimensional *cyclic polytopes*. We write $C(m, 2d)$ for the cyclic polytope with $m$ vertices of dimension $2d$; we shall define this polytope in the next section. Cyclic polytopes have been extensively studied in convex geometry, going back to [Car] in 1911. For an introduction, see [Bar, Chapter VI]. Triangulations of cyclic polytopes have been investigated with a view to extending to that setting some of the rich structure of triangulations of convex polygons (see [KV, ER]) and as a testing-ground for more general convex-geometric questions, such as the Generalized Baues Problem (see [ERR, RaS]).

In order to generalize the above perspective on triangulations of an $m$-gon to $2d$-dimensional cyclic polytopes, we need to decide what will play the role of the diagonals in the 2-dimensional case. We obtain a very natural generalization of the 2-dimensional setup by focussing on the $d$-dimensional faces of the triangulation which lie within the interior of $C(m, 2d)$. (We refer to these $d$-dimensional simplices as *internal*.) Specifically, we have the following three results, analogues of the three results mentioned above in the two-dimensional case:

1. A triangulation of $C(m, 2d)$ is determined by the $d$-dimensional faces appearing in the triangulation [Dey].

2. A collection of $d$-dimensional internal simplices of $C(m, 2d)$ of the maximal possible size such that no two intersect in their relative interiors, corresponds to a triangulation. Further, the condition that no two $d$-dimensional internal simplices intersect in their relative interiors admits a simple combinatorial description.

3. Two triangulations $S$ and $T$ of $C(m, 2d)$ are related by a bistellar flip iff they have all but one face of dimension $d$ in common.

We do not know an analogue of points 2 and 3 above in the case of odd-dimensional cyclic polytopes. Note that point 2 would need to be significantly modified, since the number of faces of a given dimension in a triangulation of $C(m, 2d+1)$ is not fixed by $m$ and $d$.

This abstract is an abridged form of the convex-geometric parts of [OT]. For more details, and complete proofs, the reader is referred to that paper.

## 1.1 Tropical cluster exchange relations

One motivation for this work is the fact that, in the $d=1$ case, triangulations of an $m$-gon form a model for the combinatorics of the $A_{m-3}$ cluster algebra in the sense that diagonals of the $m$-gon are in bijection with the cluster variables in the $A_{m-3}$ cluster algebra, and the clusters correspond to triangulations.
We might therefore hope that the internal *d*-simplices of $C(m, 2d)$ also correspond to “cluster variables” in some analogue of a cluster algebra. At present, we do not know how this should be interpreted. However, we can exhibit an analogue of the tropical cluster exchange relations of [GSV, FT] in our setting.

Let us very briefly recall the tropical cluster algebra of functions on laminations, in the rather special case which is of interest to us. Fix an *m*-gon. A *lamination* is a collection of lines in the polygon, which do not intersect, and which begin and end on the boundary of the polygon, and not on any vertex. Let $\mathcal{L}$ be the set of laminations. For any lamination $L \in \mathcal{L}$, and $E$ any boundary edge or diagonal of the polygon, there is a well-defined number of points of intersection between $L$ and $E$.

Encode this information by associating to each edge or diagonal $A$ of the polygon, a function $I_A: \mathcal{L} \to \mathbb{N}$, where $I_A(L)$ is the number of intersections between $A$ and $L$.

These functions satisfy a certain *tropical exchange relation*, namely, if $E, F, G, H$ are four sides of a quadrilateral in cyclic order, and $A, B$ are the two diagonals, then the relation is:

$$I_A + I_B = \max(I_E + I_G, I_F + I_H)$$

This relation is the tropicalization of the usual cluster relation in type $A$ (in the sense that $(\times, +)$ have been replaced by $(+, \max)$). Using this relation, and supposing that the value of the functions corresponding to the edges of a given starting triangulation (including the boundary edges) are known for a particular lamination, one can determine the value of the function corresponding to an arbitrary diagonal of the polygon (for the same lamination).

For general $d$, we define a similar collection of laminations, again denoted $\mathcal{L}$, and define functions $I_A: \mathcal{L} \to \mathbb{N}$ for each $A$ a $d$-simplex in $C(m, 2d)$ (including boundary $d$-simplices). These functions satisfy an exchange relation similar to the tropical exchange relation above, which we shall state precisely in Section 4 below.

## 1.2 Representation Theory

Another useful model for understanding (acyclic) cluster algebras is the cluster category of [BM+]. Here, the (basic) cluster-tilting objects correspond to clusters of the cluster category, or, in type $A_n$, to triangulations of a polygon. In fact, in type $A_n$, there is a similar but more elementary construction, in which the clusters of a type $A_n$ cluster algebra correspond naturally to the tilting objects of the type $A_{n+1}$ linearly oriented path algebra. A starting point for the work recorded here was the observation that a similar connection exists between the triangulations of even-dimensional cyclic polytopes and a certain natural subset of the tilting objects of a higher Auslander algebra of a type $A$ linearly oriented path algebra. The convex geometric results which we report here were needed in order to establish this fact. For more on this link, the reader is referred to [OT].

## Acknowledgements

The authors would like to thank Jesus De Loera, Osamu Iyama, Vic Reiner, Charles Paquette, and Francisco Santos for helpful conversations. S. O. was supported by NFR Storforsk grant no. 167130. H. T. was supported by an NSERC Discovery Grant. Computer calculations used ACEnet facilities, employing Sage [Sage] and the NetworkX package [HSS]. Much of this work was done during two visits by H. T. to NTNU; he thanks the Institutt for Matematiske Fag, and his hosts Idun Reiten and Aslak Bakke Buan. [OT] was completed during a visit by S. O. to UNB funded by a Harrison McCain Young Scholar award;
he thanks the math department for their hospitality. The authors also thank the referees for their helpful suggestions.

## 2 Triangulations of cyclic polytopes

The moment curve is the curve defined by $p_t = (t, t^2, \dots, t^\delta) \subset \mathbb{R}^\delta$, for $t \in \mathbb{R}$. Choose $m$ distinct real values, $t_1 < t_2 < \dots < t_m$. The convex hull of $p_{t_1}, \dots, p_{t_m}$ is a cyclic polytope. (We will take this as our definition of cyclic polytope, though sometimes a somewhat more general definition is used.)

We will be interested in triangulations of $C(m, \delta)$. A triangulation of $C(m, \delta)$ is a subdivision of $C(m, \delta)$ into $\delta$-dimensional simplices whose vertices are vertices of $C(m, \delta)$. We write $S(m, \delta)$ for the set of all triangulations of $C(m, \delta)$. A triangulation can be specified by giving the collection of $(\delta + 1)$-subsets of $\{1, \dots, m\}$ corresponding to the $\delta$-simplices of the triangulation. It turns out that whether or not a collection of $(\delta + 1)$-subsets of $\{1, \dots, m\}$ forms a triangulation is independent of the values $t_1 < \dots < t_m$ chosen, so, for convenience, we set $t_i = i$. Combinatorial descriptions of the set of triangulations of $C(m, \delta)$ appear in the literature [Ram, Tho] (and see also [DRS, Section 6.1], but for our purposes a new description is required.

We will mainly be interested in the case where $\delta = 2d$ is even. In $\mathbb{R}^{2d}$, we will refer to *upper and lower* with respect to the $2d$-th coordinate. The upper facets of $C(m, 2d)$ are those which divide $C(m, 2d)$ from points above it, while the lower facets of $C(m, 2d)$ are those which divide it from points below it. Each facet of $C(m, 2d)$ is either upper or lower.

We will be particularly interested in $d$-dimensional simplices whose vertices are vertices of $C(m, 2d)$. We refer to such $d$-dimensional simplices as $d$-dimensional simplices in $C(m, 2d)$ (leaving unstated the assumption that their vertices are vertices of $C(m, 2d)$). By convention, we record such simplices as increasing $(d+1)$-tuples from $[1, m] = \{1, 2, \dots, m\}$.

**Lemma 2.1** Let $A = (a_0, \dots, a_d)$ be a $d$-simplex in $C(m, 2d)$.

1. A lies within a lower boundary facet of $C(m, 2d)$ iff A contains $i$ and $i + 1$ for some $i$.

2. A lies within an upper boundary facet of $C(m, 2d)$ and not within any lower boundary facet iff A does not contain $i$ and $i + 1$ for any $i$, and contains both $1$ and $m$.

3. Otherwise, the relative interior of A lies in the interior of $C(m, 2d)$. We refer to such $d$-faces as internal.

**Proof:** This follows immediately from the description of the upper and lower boundary facets of $C(m, 2d)$ given in [ER, Lemma 2.3]: the lower boundary facets of $C(m, 2d)$ are precisely those simplices whose vertices are $2d$-subsets consisting of a union of $d$ pairs of the form $\{i, i + 1\}$, while the upper boundary facets are precisely those simplices whose vertices are $2d$-subsets consisting of a union of $d - 1$ pairs of the form $\{i, i + 1\}$ together with $\{1, m\}$. $\square$

We define index sets as follows:

**Definition 2.2**

$$ \mathbf{I}_m^d = \{(i_0, \dots, i_d) \in \{1, \dots, m\}^{d+1} \mid \forall x \in \{0, 1, \dots, d-1\} : i_x + 2 \le i_{x+1}\} $$

$$ \circled{\mathbf{I}}_m^d = \{(i_0, \dots, i_d) \in \mathbf{I}_m^d \mid (i_0, i_d) \neq (1, m)\}. $$
**Definition 2.3** We say that $(i_0, i_1, \dots, i_k)$ is separated if $i_x + 2 \le i_{x+1}$ for all $0 \le x \le k-1$.

Using this term, we can rephrase the definition of $\mathbf{I}_m^d$ as the set of separated $(d+1)$-tuples from $\{1, 2, \dots, m\}$.

Now Lemma 2.1 can be rephrased as saying that $\mathbf{I}_m^d$ indexes the internal $d$-simplices of $C(m, 2d)$, while $\mathbf{I}_m^d$ indexes the $d$-simplices in $C(m, 2d)$ which do not lie on a lower boundary facet.

Let $S$ be a triangulation of $C(m, 2d)$. Denote by $e(S)$ the set of $d$-simplices in $C(m, 2d)$ which appear as a face of some simplex in $S$, and which do not lie on any lower boundary facet of $C(m, 2d)$.

Let $A$ and $B$ be increasing $(d+1)$-tuples of real numbers. We say that $A = (a_0, \dots, a_d)$ intertwines $B = (b_0, \dots, b_d)$ if $a_0 < b_0 < a_1 < b_1 < \dots < a_d < b_d$. We write $A \sim B$ for this relation. A collection of increasing $(d+1)$-tuples is called *non-intertwining* if no pair of the elements intertwine (in either order).

**Theorem 2.4** For any $S \in S(m, 2d)$ the set $e(S)$ consists of exactly $\binom{m-d-1}{d}$ elements of $\mathbf{I}_m^d$, and is non-intertwining.

We also have a converse result:

**Theorem 2.5** Any non-intertwining collection of $\binom{m-d-1}{d}$ elements of $\mathbf{I}_m^d$ is $e(S)$ for a unique $S \in S(m, 2d)$.

**Example 2.6** We consider the above theorems in the case $d=1$. If $S$ is a triangulation of $C(m, 2d)$, then $e(S)$ consists of the internal edges of the triangulation together with the edge $1m$. The theorems are clear in this case.

## 2.1 Proof of Theorem 2.4

An affine dependency among vectors $\{v_1, \dots, v_r\}$ in $\mathbb{R}^e$ is a relation of the form $\sum a_i v_i = 0$ where $\sum a_i = 0$, but the coefficients are not all zero. We now describe the minimal-size affine dependencies among points on the moment curve. Proofs of the following can be found in [ER, OT].

**Lemma 2.7** Let $a_1 < \dots < a_{2d+2}$. Among the points $p_{a_1}, \dots, p_{a_{2d+2}}$ there is a unique affine dependency, which can be expressed in the form

$$ \sum_{i \text{ even}} c_i p_{a_i} = \sum_{i \text{ odd}} c_i p_{a_i} $$

where the $c_i$ are all positive and

$$ \sum_{i \text{ even}} c_i = 1 = \sum_{i \text{ odd}} c_i $$

The previous lemma can also be expressed as saying that if $X$ and $Y$ are intertwining $(d+1)$-tuples, then the corresponding $d$-simplices intersect in a single interior point of both, while if $X$ and $Y$ are distinct $(d+1)$-tuples which do not intertwine, the relative interiors of their corresponding simplices are disjoint.

For $A = (a_0, \dots, a_{2d})$ an increasing $(2d+1)$-tuple from $[1, m]$, define the $(d+1)$-tuple $e(A) = (a_0, a_2, \dots a_{2d})$ by taking the even-index terms from $A$.

**Proof of Theorem 2.4:** The elements of $e(S)$ are faces of simplices in the triangulation. Thus, they cannot intersect in a single point in both their interiors. It follows that $e(S)$ is non-intertwining.

We now establish the cardinality of $e(S)$. It turns out that $E \in e(S)$ iff $E = e(A)$ for some simplex $A$ of $S$, and, for different simplices $A, B$ of $S$, we have $e(A) \neq e(B)$. Therefore, $|e(S)|$ equals the number of simplices in $S$, which was shown by Bayer [Bay] to be $\binom{m-d-1}{d}$. $\square$
## 2.2 Proof of Theorem 2.5

To prove this theorem, we need to show the existence of certain triangulations of $C(m, 2d)$. The approach we take is inductive, and is based on some results of Rambau and Santos [RaS], which we now describe.
To begin with, we define two operations of triangulations, following [RaS, Section 3].

**Definition 2.8** Let $S \in S(m, 2d)$.

1. We define $S/1$ to be the triangulation of $C([2, m], 2d)$ which is obtained from $S$ by moving the vertices 1 and 2 together and throwing away the simplices that degenerate. The $2d$-simplices of $S/1$ are obtained from the $2d$-simplices of $S$ by removing any simplex containing both vertices 1 and 2, and then, in any simplex containing 1, replacing 1 by 2.

2. We define $S \setminus 1$ to be the triangulation of $C([2, m], 2d-1)$ obtained by taking only the simplices of $S$ that contain 1, and then removing 1 from them. This clearly defines a triangulation of the vertex figure of $C(m, 2d)$ at 1, that is to say, of the $(2d-1)$-dimensional polytope obtained by intersecting $C(m, 2d)$ with a hyperplane which cuts off the vertex 1. This vertex figure is not a cyclic polytope according to our definition, but its vertices determine the same oriented matroid as the vertices of a cyclic polytope, which is sufficient to imply that a triangulation of the vertex figure also determines a triangulation of $C([2, m], 2d-1)$, and conversely (see [RaS, Lemma 3.1] for details). We write $S \setminus \{1, 2\}$ for $(S \setminus 1) \setminus 2$.

For a triangulation $Q$ of $C(p, \delta)$ and a triangulation $P$ of $C(p, \delta - 1)$, we write that $P \prec Q$ if each simplex of $P$ is a facet of at least one simplex of $Q$. In this case, the simplices of $Q$ are divided into two classes, those above $P$ and those below $P$.

We have the following proposition, which we cite in a convenient form, restricted to the case which is of interest to us. (As it appears in [RaS], it treats subdivisions of cyclic polytopes which are more general than triangulations.)

**Proposition 2.9 ([RaS, Lemma 4.7(1)])** Let $T$ be a triangulation of $C([2, m], 2d)$, and let $W$ be a triangulation of $C([3, m], 2d-2)$. Then there exists a triangulation $S$ of $C(m, 2d)$ with $S/1 = T$ and $S \setminus \{1, 2\} = W$ iff $W \prec T \setminus 2$.

We next define two operations on subsets of $I_m^d$, parallel to the above operations on triangulations.

For an *e*-tuple $A = (a_1, \dots, a_e)$ with $a_1 > 1$ we denote by $1 \star A$ the $(e+1)$-tuple $(1, a_1, \dots, a_e)$. For a set $X$ of *e*-tuples with this property we denote by $1 \star X$ the set $\{1 \star A \mid A \in X\}$. Similarly we define $2 \star A$ and $2 \star X$.

**Definition 2.10** Let $X \subset I_m^d$. We define $X/1$ and $X \setminus \{1, 2\}$ as follows:

1. $X/1$ is obtained from $X$ by replacing all 1's by 2's, and removing any resulting tuples which are not separated.

2. $X \setminus \{1, 2\}$ consists of all $d$-tuples $A$ from $[3, m]$ such that $1 \star A$ is in $X$ and either $2 \star A$ is in $X$ or $3 \in A$. (These two possibilities are mutually exclusive, since if $3 \in A$, then $2 \star A$ is not separated, and so it cannot be in $X$.)

Note that for $X \subset I_m^d$, we do not define $X \setminus 1$; instead, we define $X \setminus \{1, 2\}$ in one step.

The relationship between the operations on triangulations and the operations on subsets of $I_m^d$ are what one might expect from the notation:
**Lemma 2.11** Let $S \in S(m, 2d)$. Then $e(S/1) = e(S)/1$, and $e(S \setminus \{1, 2\}) = e(S) \setminus \{1, 2\}$.

We next show some properties about these operations on subsets of $\mathbf{I}_m^d$.

**Lemma 2.12** If $X$ is a non-intertwining subset of $\mathbf{I}_m^d$, so are $X/1$ and $X \setminus \{1, 2\}$.

The following lemma is established by induction on $m$ and $d$:

**Lemma 2.13** The maximal size of a non-intertwining subset of $\mathbf{I}_m^d$ is $\binom{m-d-1}{d}$. Also, if $X$ is a set of that size, $|X/1| = \binom{m-d-2}{d}$, and $|X \setminus \{1, 2\}| = \binom{m-d-2}{d-1}$.

**Lemma 2.14** If $X$ and $Y$ are non-intertwining subsets of $\mathbf{I}_m^d$ of cardinality $\binom{m-d-1}{d}$ such that $X/1 = Y/1$ and $X \setminus \{1, 2\} = Y \setminus \{1, 2\}$, then $X = Y$.

**Proof of Theorem 2.5:** Suppose that we have a non-intertwining set $X \subset \mathbf{I}_m^d$ of cardinality $\binom{m-d-1}{d}$. We want to show that it defines a unique triangulation. The proof is by induction on $d$ and $m$.

By Lemma 2.13, $|X/1| = \binom{m-d-2}{d}$ and $|X \setminus \{1, 2\}| = \binom{m-d-2}{d-1}$. It follows by induction that $X/1$ and $X \setminus \{1, 2\}$ define unique triangulations, of $C([2, m], 2d)$ and $C([3, m], 2d-2)$, respectively, which we can denote $T$ and $W$. We then show that $W \prec T \setminus 2$.

Proposition 2.9 implies that there is a unique triangulation $S$ such that $S/1 = T$ and $S \setminus \{1, 2\} = W$. We know that $e(S)/1 = X/1$ and $e(S) \setminus \{1, 2\} = X \setminus \{1, 2\}$. By Lemma 2.14, $X = e(S)$. By the result of Dey already cited, $S$ is the only triangulation with $e(S) = X$. $\square$

The unique triangulation corresponding to a maximal-size collection of non-intertwining subsets of $\mathbf{I}_m^d$ is easy to construct.

**Proposition 2.15** The triangulation corresponding to a set $X$ of $\binom{m-d-1}{d}$ non-intertwining elements of $\mathbf{I}_m^d$ consists of precisely the simplices all of whose $d$-faces are either non-separated or contained in $X$.

**Proof:** This is a refinement of the result of Dey [Dey] specialized to our setting and is proved similarly. $\square$

<figure><img src="image_1.png" /></figure>

# 3 Bistellar flips

**Theorem 3.1** For $S, T \in S(m, 2d)$, we have that $S$ and $T$ are related by a bistellar flip iff $e(S)$ and $e(T)$ have all but one $(d+1)$-tuple in common. In this case, the two $(d+1)$-tuples in the symmetric difference of $e(S)$ and $e(T)$ intertwine.

**Example 3.2** When $d=1$ and the vertices are in convex position, a bistellar flip amounts to replacing one diagonal of a quadrilateral with the other diagonal. The vertices of $C(m, 2)$ are always in convex position, so bistellar flips always amount to replacing one diagonal of a quadrilateral by the other one; clearly, if $S$ and $T$ are related in this way, then $e(S)$ and $e(T)$ differ by the diagonal being flipped.

If $A \in \mathbf{I}_m^d$ and $R$ is a non-intertwining subset of $\mathbf{I}_m^d$ not containing $A$, we say that $A$ is a complement for $R$ if $R \cup \{A\}$ corresponds to a triangulation (that is to say, it is non-intertwining and has cardinality $\binom{m-d-1}{d}$).

If $A$ and $B$ are distinct complements to some $R$, they are called *exchangeable*.

**Proposition 3.3** *A and B are exchangeable iff they intertwine (in some order).*
**Proposition 3.4** Let A and B be exchangeable. A and B are complements to $R \subset \mathbf{I}_m^d$ iff R is a non-intertwining subset of $\mathbf{I}_m^d \setminus \{A, B\}$ with cardinality $\binom{m-d-1}{d}-1$, which contains every separated $(d+1)$-tuple from $A \cup B$ other than A and B.

**Example 3.5** In the $d=1$ case, it is clear that A and B are exchangeable iff they cross in their interiors (as line segments) iff they intertwine in some order (as increasing ordered pairs from $\{1, \dots, m\}$). In this case, the triangulations in which A can be exchanged for B are exactly those containing A and the four edges of the quadrilateral defined by the vertices of A and B.

# 4 Tropical cluster exchange relations

Define a generalized lamination to be a finite collection of increasing $(d+1)$-tuples from $\mathbb{R}\setminus\{1, \dots, m\}$, such that no two intertwine. We can also think of a generalized lamination as a collection of $d$-simplices in $\mathbb{R}^{2d}$ with vertices on the moment curve, which do not intersect in their interiors; the increasing $(d+1)$-tuple $(b_0, \dots, b_d)$ corresponds to the convex hull of the points $p_{b_i}$. We denote by $\mathcal{L}$ the set of all generalized laminations.

For each increasing $(d+1)$-tuple $A$ from $\{1, \dots, m\}$ we define a function $I_A: \mathcal{L} \to \mathbb{N}$ by setting $I_A(L)$ to be the number of elements of $L$ which intertwine with $A$ (in some order). This is also equal to the number of intersections of the simplex $A$ with the simplices defined by the lamination. In this section we show that these functions satisfy certain tropical exchange relations which we shall define, and in which the functions $I_A$ for $A \notin \mathcal{O} \mathbf{I}_m^d$ function as frozen variables (in other words, they cannot be mutated).

In the case that $d=1$, this was shown by Gekhtman, Shapiro, and Vainshtein [GSV]. ([GSV] considers more general situations, where the polygon is replaced by other surfaces. See also the work of Fomin and Thurston [FT] for another perspective and further extensions of this.)

The next theorem gives the tropical exchange relation between $I_A$ and $I_B$ where A and B are exchangeable. First we need a definition:

**Definition 4.1** For $(i_0, \dots, i_d), (j_0, \dots, j_d) \in \mathcal{O} \mathbf{I}_{n+2d+1}^d$ with $(i_0, \dots, i_d) \prec (j_0, \dots, j_d)$, and $X \subseteq \{0, \dots, d\}$, we set

$$m_X((i_0, \dots, i_d), (j_0, \dots, j_d)) = \text{sort}(\{i_x \mid x \in X\} \cup \{j_x \mid x \notin X\})$$
$$n_X((i_0, \dots, i_d), (j_0, \dots, j_d)) = \text{sort}(\{i_x \mid x \in X\} \cup \{j_{x-1} \mid x \notin X\})$$

Here we write $\text{sort}(K)$ for the tuple consisting of the elements of the set $K$ in increasing order. In the definition of $n_X$, we interpret $j_{-1}$ as $j_d$.

**Theorem 4.2** Let $A, B \in \mathcal{O} \mathbf{I}_m^d$ such that $A \prec B$. Then we have the following equality of functions $\mathcal{L} \to \mathbb{Z}$:

$$I_A = \max \left( \sum_{X \subseteq \{0, \dots, d\}} (-1)^{|X|+d} I_{m_X(A,B)}, \sum_{X \subseteq \{0, \dots, d\}} (-1)^{|X|+d} I_{n_X(A,B)} \right) \quad (1)$$

The relation (1) is “tropical” because it uses the operations $\max(\cdot, \cdot)$ and $+$, rather than $+$ and $\times$.
If $d = 1$, and $A = (a_0, a_1)$, $B = (b_0, b_1)$, then (1) specializes to:

$$I_{(a_0,a_1)} = \max (I_{(a_0,b_1)} + I_{(b_0,a_1)} - I_{(b_0,b_1)}, I_{(a_0,b_0)} + I_{(a_1,b_1)} - I_{(b_0,b_1)}) \quad (2)$$

If one replaces $(\max, +)$ in (2) with $(+, \times)$, one obtains the type A cluster algebra exchange relation. We do not know how to obtain a meaningful analogue of this for $d > 1$.

Note that for $d > 1$, (1) is not a tropical cluster algebra relation, because of the signs. When $d = 2$, we get, for example, the following exchange relation:

$$I_{024} - I_{135} = \max(I_{124} + I_{034} + I_{025} - I_{134} - I_{125} - I_{035}, \\ I_{245} + I_{014} + I_{023} - I_{013} - I_{145} - I_{235})$$

The statement of Theorem 4.2 was chosen for maximum uniformity. It follows from the proof that, if $d$ is even, then the two terms inside the $\max(\cdot, \cdot)$ are equal, so the theorem could be stated more simply in this case.

## 4.1 Proof of Theorem 4.2

Let $\ell = (\ell_0, \dots, \ell_d)$ be an increasing $(d+1)$-tuple of non-integers. We will also write $\ell$ for the generalized lamination consisting only of $\ell$. We begin by considering (1) on generalized laminations of the form $\ell$.

A simple analysis of the combinatorics implies:

**Proposition 4.3** Let A and B be exchangeable $(d+1)$-tuples such that $A \backslash B$, and let $\ell$ be as above. Then exactly one of the following happens:

$$1. \sum_{X \subseteq \{0, \dots, d\}} (-1)^{|X|} I_{m_X(A,B)}(\ell) = 0, \text{ or}$$

$$2. d \text{ is odd, and } a_i < \ell_i < b_i \text{ for all } i.$$

We say that $\ell$ is in $m$-special position with respect to the pair A, B if it satisfies Condition (2) of Proposition 4.3.

Under the same conditions of Proposition 4.3, a similar statement holds for $\sum_{X \subseteq \{0, \dots, d\}} (-1)^{|X|} I_{n_X(A,B)}(\ell)$; either this sum is zero or $d$ is odd and there is one entry $\ell_k$ between $b_{i-1}$ and $a_i$ for all $1 \le i \le d$, and one entry $\ell_k$ which is either less than $a_0$ or greater than $b_d$. If the second of these two alternatives holds, we say that $\ell$ is in $n$-special position.

**Proof of Theorem 4.2:** Consider (1) applied on $\ell$. By the above proposition (and its analogue), if $d$ is even, or if $\ell$ is neither in $m$- nor $n$-special position, then the contributions from $\ell$ to both sides of (1) are equal and, further, the two terms being maximized are also equal. In the remaining case ($d$ odd and $\ell$ in $m$- or $n$-special position), one checks that the lefthand side of (1) is 1, while the terms on the righthand side are $-1$ and $1$.

Now we consider (1) on an arbitrary generalized lamination $L$. As already observed, the simplices in $L$ which are neither in $m$- nor $n$-special position with respect to A, B give equal contributions to the left-hand side of (1) and to each of the terms of the maximum on the right-hand side, so they can be ignored. If $d$ is even, we are done also. Otherwise, note that $L$ cannot have both elements which are in $m$-special position and elements which are in $n$-special position, since these would intertwine. Thus, only one of the two special positions is allowed, and the contributions from all the terms of $L$ in special position therefore appear, with positive sign, in the same term in the maximum. Thus the equality of the theorem holds. $\square$
# 5 New phenomena in higher dimensions

In this section we consider the simplicial complex $\Delta_m^{2d}$ with vertex set $\mathring{\mathbf{I}}_m^d$, whose maximal faces correspond to the collections of internal simplices of triangulations of $C(m, 2d)$. We report on some features of $\Delta_m^{2d}$ for $d = 1$ which do not persist for higher $d$.

## 5.1 The clique property

Given a simplicial complex $\Delta$ on a vertex set $V$, we say that vertices $v$ and $w$ are compatible if $\{v, w\}$ is a face of $\Delta$. We then say that $\Delta$ is a *clique complex* if its faces consist of all pairwise compatible subsets of $V$. The complex $\Delta_m^2$ is clique, because any maximal collection of non-crossing diagonals corresponds to a triangulation. This property no longer holds for $\Delta_m^{2d}$ with $d \ge 3$.

**Proposition 5.1** $\Delta_{2d+3}^{2d}$ is not a clique complex for $d \ge 3$. Equivalently, there exist maximal non-intertwining subsets of $\mathring{\mathbf{I}}_{2d+3}^d$ which are not of the overall maximal size.

Computer experiments have not detected any similar phenomena when $d=2$.

**Proof of Proposition 5.1:** The elements of $\mathring{\mathbf{I}}_{2d+3}^d$ can be arranged in a cycle, in such a fashion that any $(d+1)$-tuple is compatible with any other one except the two which are maximally distant from it. The overall maximal size of a non-intertwining collection is $d+1$; the non-intertwining collections of that size consist of $d+1$ consecutive entries around the cycle.

For $d=3$, the resulting cycle is below:

<figure><img src="image_2.png" /></figure>

If $d \ge 3$, it is possible to choose three $(d+1)$-tuples in $\mathring{\mathbf{I}}_{2d+3}^d$ which are pairwise non-intertwining, but which do not all lie in any consecutive sequence of length $d+1$. Therefore, this collection cannot be extended to a collection of $d+1$ non-intertwining elements of $\mathring{\mathbf{I}}_{2d+3}^d$.

For example, for $d=3$, we could choose $\{1357, 1468, 2479\}$ as our starting collection; it is impossible to increase it to a non-intertwining collection of size $d+1=4$. $\square$

## 5.2 Shellability

It is natural to ask about the topology of $\Delta_m^{2d}$. Many nice simplicial complexes are *shellable*. We recall the precise definition below; the point is that if a simplicial complex is shellable, then its homotopy
type admits a very simple description. It is classical that $\Delta_m^2$ is shellable, because it can be realized as the boundary of a convex polytope, the (simple) associahedron [Lee], and the boundary of a simplicial convex polytope is shellable [BrM].

Our result in this direction is a negative one:

**Proposition 5.2** For $d \ge 2$, the complex $\Delta_{2d+3}^{2d}$ is not shellable.

A simplicial complex is called $d$-dimensional if all its maximal faces contain $d+1$ vertices.

**Definition 5.3** For $d > 0$, a $d$-dimensional simplicial complex is called shellable if its maximal faces admit an order $F_1, \dots, F_p$ such that for all $i > 1$, the intersection of $F_i$ with $\bigcup_{j<i} F_j$ is a non-empty union of codimension one faces of $F_i$.

If a $d$-dimensional simplicial complex is shellable, then it is either contractible or homotopic to the wedge product of some number of $d$-dimensional spheres, [Bjö, Theorem 1.3].

**Proof of Proposition 5.2:** The simplicial complex $\Delta_{2d+3}^{2d}$ is $d$-dimensional. Therefore, if $\Delta_{2d+3}^{2d}$ were shellable, it would necessarily either be contractible or be homotopic to a wedge of some number of $d$-spheres.

The cycle defined in the proof of Proposition 5.1 on the vertices of $\Delta_{2d+3}^{2d}$, viewed as a one-dimensional simplicial complex, is a subcomplex of $\Delta_{2d+3}^{2d}$, and $\Delta_{2d+3}^{2d}$ admits a deformation retract to it. Thus $\Delta_{2d+3}^{2d}$ is homotopic to $S^1$. It follows that for $d \ge 2$ it is not shellable. $\square$

## References

[Bay] Margaret Bayer, Equidecomposable and weakly neighborly polytopes. *Israel J. Math.* 81 (1993) no. 3, 301–320.

[Bar] Alexander Barvinok. *A course in convexity*. Graduate studies in mathematics Vol. 54, American Mathematical Society, Providence, RI, 2002.

[Bjö] Anders Björner. Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings. *Adv. in Math.* 52 (1984), no. 3, 173–212.

[BrM] H. Bruggesser and P. Mani. Shellable decompositions of cells and spheres. *Math. Scand.* 29 (1971), 197–205.

[BM+] Aslak Bakke Buan, Robert Marsh, Markus Reinecke, Idun Reiten, and Gordana Todorov. Tilting theory and cluster combinatorics. *Adv. Math.* 204 (2006), no. 2, 572–618.

[Car] Constantin Carathéodory. Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen. *Rend. Circ. Mat. Palermo* 32 (1911), 193–217.

[Dey] Tamal Krishna Dey. On counting triangulations in $d$ dimensions. *Computational Geometry* 3 (1993), no. 6, 315–325.

[DRS] Jesús de Loera, Jörg Rambau, and Francisco Santos. *Triangulations. Structures for algorithms and applications*. Algorithms and Computation in Mathematics, 25. Springer-Verlag, Berlin, 2010.
[ER] Paul Edelman and Victor Reiner. The higher Stasheff-Tamari posets. *Mathematika* 43 (1996), no. 1, 127–154.

[ERR] Paul Edelman, Jörg Rambau, and Victor Reiner. On subdivision posets of cyclic polytopes. *Combinatorics of polytopes*. *European J. Combinatorics* 21 (2000), no. 1, 85–101.

[FG] Vladimir Fock and Alexander Goncharov. Moduli spaces of local systems and higher Teichmüller theory. *Publ. Math. Inst. Hautes Études Sci.* No. 103 (2006), 1–211.

[FST] Sergey Fomin, Michael Shapiro, and Dylan Thurston. Cluster algebras and triangulated surfaces. *I. Cluster complexes*. *Acta Math.* 201 (2008), no. 1, 83–146.

[FT] Sergey Fomin and Dylan Thurston. Cluster algebras and triangulated surfaces. Part II: Lambda lengths. Preprint, 2008. Available at http://www.math.lsa.umich.edu/~fomin/papers.html

[FZ] Sergey Fomin and Andrei Zelevinsky. Cluster algebras I: Foundations. *J. Amer. Math. Soc.* 15 (2002), no. 2, 497–529.

[GSV] Michael Gekhtman, Michael Shapiro, and Alek Vainshtein. Cluster algebras and Weil-Petersson forms. *Duke Math J.* 127 (2005), no. 2, 291–311.

[HSS] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using NetworkX, in *Proceedings of the 7th Python in Science Conference (SciPy2008)*. Gäel Varoquaux, Travis Vaught, and Jarrod Millman (eds.). Pasadena, CA, pp. 11–15, 2008.

[KV] Mikhail Kapranov and Vladimir Voevodsky. Combinatorial-geometric aspects of polycategory theory: pasting schemes and higher Bruhat orders (list of results). International Category Theory Meeting (Bangor, 1989 and Cambridge, 1990). *Cahiers Topologie Géom. Différentielle Catég.* 32 (1991), no. 1, 11–27.

[Lee] Carl Lee. The associahedron and triangulations of the $n$-gon. *European J. Combin.* 10 (1989), no. 6, 551–560.

[OT] Steffen Oppermann and Hugh Thomas. Higher dimensional cluster combinatorics and representation theory. *J. European Mathematical Society* (to appear), arXiv:1001.5437.

[Ram] Jörg Rambau. Triangulations of cyclic polytopes and higher Bruhat orders. *Mathematika* 44 (1997), no. 1, 162–194.

[RaS] Jörg Rambau and Francisco Santos. The generalized Baues problem for cyclic polytopes. *I. European J. Combin* 21 (2000), no. 1, 65–83.

[Sage] William Stein. *Sage: Open Source Mathematical Software (version 3.2.3)*. The Sage Group, 2009, http://www.sagemath.org.

[Tho] Hugh Thomas. New combinatorial descriptions of the triangulations of cyclic polytopes and the second higher Stasheff-Tamari posets. *Order* 19 (2002), no. 4, 327–342.