# Newton Polytopes of Cluster Variables of Type $A_n$

Adam Kalman*

Department of Mathematics, University of California, Berkeley, CA 94720, USA

**Abstract.** We study Newton polytopes of cluster variables in type $A_n$ cluster algebras, whose cluster and coefficient variables are indexed by the diagonals and boundary segments of a polygon. Our main results include an explicit description of the affine hull and facets of the Newton polytope of the Laurent expansion of any cluster variable, with respect to any cluster. In particular, we show that every Laurent monomial in a Laurent expansion of a type A cluster variable corresponds to a vertex of the Newton polytope. We also describe the face lattice of each Newton polytope via an isomorphism with the lattice of elementary subgraphs of the associated snake graph.

**Résumé.** Nous étudions polytopes de Newton des variables amassées dans les algèbres amassées de type A, dont variables sont indexés par les diagonales et les côtés d'un polygone. Nos principaux résultats comprennent une description explicite de l'enveloppe affine et facettes du polytope de Newton du développement de Laurent de toutes variables amassées. En particulier, nous montrons que tout monôme Laurent dans un développement de Laurent de variable amassée de type A correspond à un sommet du polytope de Newton. Nous décrivons aussi le treillis des faces de chaque polytope de Newton via un isomorphisme avec le treillis des sous-graphes élémentaires du "snake graph" qui est associé.

**Keywords:** cluster algebra, Newton polytope, triangulated surfaces

## 1 Introduction

Cluster algebras, introduced by Fomin and Zelevinsky in the early 2000's [10], are a class of commutative rings equipped with a distinguished set of generators (*cluster variables*) that are grouped into sets of constant cardinality $n$ (the *clusters*). A cluster algebra may be defined from an initial cluster $(x_1, \dots, x_m)$ and a quiver, which contains combinatorial data for the process of *mutation*, in which new clusters and quivers are created recursively from old ones. There may also be coefficients involved in the construction. The *cluster algebra* is the algebra generated by all cluster variables, after mutation is repeated ad infinitum.

Perhaps the most fundamental example of a cluster algebra is the cluster algebra associated with triangulations of a polygon. Cluster algebras of finite type (i.e. those with finitely many cluster variables)

<footnote>*Email: akalman@math.berkeley.edu</footnote>
are classified by Dynkin diagrams, and the cluster algebras coming from triangulations of a polygon are precisely those of type *A*. In this model, diagonals correspond to cluster variables, triangulations (i.e. maximal collections of non-intersecting diagonals) correspond to clusters, boundary segments correspond to coefficient variables, and mutation corresponds to a local move called a *flip* of the triangulation, in which one diagonal is replaced with another one.

A consequence of the definition of cluster algebra is that every cluster variable is a rational function in the initial cluster variables, but more strongly, the remarkable *Laurent Phenomenon* [10] states that every cluster variable is in fact a Laurent polynomial in those variables. In the last ten years, much work has been done on Laurent expansion formulas for cluster algebras. Carroll and Price (in unpublished results [2]) were the first to discover formulas for Laurent expansions of cluster variables in the case of a triangulated polygon, writing one formula in terms of paths on the triangulation, and another in terms of perfect matchings of so-called *snake graphs* [20]. Schiffler rediscovered these paths, calling them “T-paths,” and the path and snake graph formulas were subsequently reworked and generalized by Schiffler and others in a series of works [22], [24], [17], [18], with [18] providing Laurent expansions of cluster variables associated to cluster algebras from arbitrary surfaces.

In this paper, we study the Newton polytope of the Laurent expansion of a type *A* cluster variable with respect to an arbitrary cluster. The study of Newton polytopes of Laurent expansions of cluster variables was initiated by Sherman and Zelevinsky in their study of rank 2 cluster algebras, in which it was shown that the Newton polygon of any cluster variable in a rank 2 cluster algebra of finite or affine type is a triangle [25]. We will extend these results in type *A* by considering cluster algebras of arbitrary rank. Another motivation for this study is that understanding Newton polytopes of cluster variables has been useful for understanding positivity properties of certain bases of cluster algebras [3, 25].

Our first main result in this paper is Theorem 3.12, a description of the face lattice of the Newton polytope of a Laurent expansion of any cluster variable of type $A_n$ via an isomorphism with the lattice of elementary subgraphs of the associated snake graph. Our second main result is Theorem 3.17, which gives an explicit description of the affine hull and facets of such a polytope that can be read off the triangulation directly. We also show in Corollary 3.13 that every Laurent monomial in a Laurent expansion of a type *A* cluster variable corresponds to a vertex of the Newton polytope.

The structure of this paper is as follows. Section 2 contains a summary of the formula that gives cluster expansions using perfect matchings. Section 3 establishes necessary definitions and notation, then states our main results and other more peripheral results along the way. In Section 4, we discuss progress toward more general results. For full proofs of all results in this paper, see [15].

## 2 Cluster Expansions from Matchings

The cluster algebra we are considering in this paper is constructed from a triangulation $T$ of an $(n+3)$-gon as follows. Let $\tau_1, \tau_2, \dots, \tau_n$ be the $n$ diagonals of $T$, and let $\tau_{n+1}, \tau_{n+2}, \dots, \tau_{2n+3}$ be the $n+3$ boundary segments.

The quiver $Q_T$ is defined as follows: place a frozen vertex at the midpoint of each boundary segment of the polygon, and place a mutable vertex at the midpoint of each diagonal (see Figure 1). These midpoint
vertices form the vertices of $Q_T$. Label these vertices according to the labeling of the polygon. To form the arrows of $Q_T$, go to each triangle of $T$ and inscribe a new triangle connecting the midpoint vertices, orienting the arrows clockwise within this new triangle. For example, here is a triangulation $T$ of a hexagon, along with the corresponding quiver $Q_T$. The diagonals and boundary segments of $T$ are shown as thin solid lines. Mutable vertices of the quiver are indicated by filled-in circles, frozen vertices are indicated by unfilled circles, and the arrows of the quiver are dashed lines.

<figure><img src="image_1.png" /><figcaption>Fig. 1: The quiver $Q_T$</figcaption></figure>

Let $\mathcal{A}(Q_T)$ be the cluster algebra with initial cluster variables $(x_1, \dots, x_n)$, coefficient variables $(x_{n+1}, \dots, x_{2n+3})$, and initial quiver $Q_T$. Each cluster variable in $\mathcal{A}(Q_T)$ corresponds to a diagonal. Let $x_\gamma$ be the cluster variable corresponding to the diagonal $\gamma$.

The cluster expansion of $x_\gamma$ with respect to $T$, or the $T$-expansion of $x_\gamma$, means the Laurent polynomial (equal to $x_\gamma$) in the variables which each correspond to a diagonal or boundary segment of $T$. The formula for the $T$-expansion of $x_\gamma$ in [17] for the cluster variables is given in terms of perfect matchings of a graph $G_{T,\gamma}$ that is constructed using recursive gluing of tiles. We now recount the construction of this graph $G_{T,\gamma}$, as described in [17] and [18]. The reader may wish to refer to Figure 2 as an example.

Let $\gamma$ be a diagonal which is not in $T$. Choose an orientation on $\gamma$, and let the points of intersection of $\gamma$ and $T$, in order, be $p_0, p_1, \dots, p_{d+1}$. Let $\tau_{i_1}, \tau_{i_2}, \dots, \tau_{i_d}$ be the diagonals of $T$ that are crossed by $\gamma$, in order. For $k$ from 0 to $d$, let $\gamma_k$ denote the segment of the path $\gamma$ from $p_k$ to $p_{k+1}$. Note that each $\gamma_k$ lies in exactly one triangle in $T$, and for $1 \le k \le d-1$, the sides of this triangle are $\tau_{i_k}, \tau_{i_{k+1}}$, and a third edge denoted by $\tau_{[\gamma_k]}$.

A tile $\bar{S}_k$ is a 4-vertex graph consisting of a square along with one of its diagonals. Any diagonal $\tau_k \in T$ is the diagonal of a unique quadrilateral $Q_{\tau_k}$ in $T$ whose sides we will call $\tau_a, \tau_b, \tau_c, \tau_d$. Associate to this quadrilateral a tile $\bar{S}_k$ by assigning weights to the diagonal and sides of $\bar{S}_k$ such that there is a homeomorphism $Q_{\tau_k} \to \bar{S}_k$ mapping the diagonal $\tau_i$ to the edge with weight $x_i$, for $i = a, b, c, d, k$.

For each tile $\bar{S}_{i_1}, \bar{S}_{i_2}, \dots, \bar{S}_{i_d}$, we choose a planar embedding in the following way: For $\bar{S}_{i_1}$, the homeomorphism $Q_{\tau_{i_1}} \to \bar{S}_{i_1}$ must be orientation-preserving, and the vertex of $\bar{S}_{i_1}$ which corresponds to $p_0$ is placed in the southwest corner. Then, for $2 \le k \le d$, choose a planar embedding for $\bar{S}_{i_k}$ which has the opposite orientation of the previous tile $\bar{S}_{i_{k-1}}$, and orient the tile $\bar{S}_{i_k}$ so that the diagonal goes from
northwest to southeast.

We then create the graph $\overline{G}_{T,\gamma}$ by gluing together tiles $\overline{S}_{i_1}, \overline{S}_{i_2}, \dots, \overline{S}_{i_d}$, in order, attaching $\overline{S}_{i_{k+1}}$ to $\overline{S}_{i_k}$ along the edge on each tile that is labeled $x_{[\gamma_k]}$. Note that the edge weighted $x_{[\gamma_k]}$ is either the northern or the eastern edge of the tile $\overline{S}_{i_k}$, and hence $\overline{G}_{T,\gamma}$ is constructed from the bottom left (the first tile) to the upper right (the last tile).

**Definition 2.1.** The snake graph $G_{T,\gamma}$ is the graph obtained from $\overline{G}_{T,\gamma}$ after the diagonal is removed from each tile.

See Figure 2 for an example of a triangulation $T$ (along with distinguished diagonal $\gamma$) and the corresponding snake graph.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** A triangulation and corresponding snake graph</figcaption></figure>

**Definition 2.2.** A perfect matching of a graph is a subset of the edges so that each vertex is covered exactly once. The weight $w(M)$ of a perfect matching $M$ is the product of the weights of all edges in $M$.

With this setup, Laurent expansions of cluster variables can be expressed in terms of perfect matchings as follows (see [17]).

**Proposition 2.3.** With the above notation,

$$x_{\gamma} = \sum_{M} \frac{w(M)}{x_{i_1} x_{i_2} \dots x_{i_d}},$$

where the sum is over all perfect matchings $M$ of $G_{T,\gamma}$.

# 3 Main Results

Before we can state our results, we need a few more definitions and some new notation.
**Definition 3.1.** The Newton polytope of a Laurent polynomial is the convex hull of all the exponent vectors of the monomials, i.e. the convex hull of all points $(c_1, c_2, ...)$ such that the monomial $x_1^{c_1} x_2^{c_2} ...$ appears with a nonzero coefficient in the Laurent polynomial.

For ease of notation, we may sometimes say a diagonal or boundary segment of the polygon is labeled $k$ rather than $\tau_k$.

**Notation 3.2.** • Let $D(\gamma)$ be the set of diagonals of the triangulation that $\gamma$ crosses, i.e. $\{\tau_{i_1}, \dots, \tau_{i_d}\}$.

• Let $T'$ be the subset of $T$ that includes all vertices incident to a diagonal in $\gamma \cup D(\gamma)$, and all diagonals and boundary segments connecting these vertices to each other.

• For any point $w \in T$, let *diagonals*($w$) := {$e \in (\gamma \cup D(\gamma)) : e \not\in w$}, the set of diagonals in $\gamma \cup D(\gamma)$ incident to $w$.

• Let the set of distinct labels of edges incident to a vertex $v \in G_{T,\gamma}$ be $E_v$. If $V$ is a collection of vertices, let $E_V := \bigcup_{w \in V} E_w$

• Let $N(T, \gamma)$ be the Newton polytope (in $\mathbb{R}^{2n+3}$) of the $T$-expansion of the cluster variable $x_\gamma$.

• Let $P(G_{T,\gamma})$ be the polytope in $\mathbb{R}^{2n+3}$ that is the convex hull of the characteristic vectors of all perfect matchings of $G_{T,\gamma}$.

**Remark 3.3.** By Proposition 2.3, the two polytopes $N(T, \gamma)$ and $P(G_{T,\gamma})$ are isomorphic, differing only by a translation by the vector $\mathbb{1}_{D(\gamma)}$ (i.e. the vector whose $i^{th}$ coordinate is 1 if $i \in D(\gamma)$, 0 otherwise). So $P(G_{T,\gamma})$ can be thought of as the “Newton polytope of the numerator” of the cluster variable corresponding to $\gamma$.

**Definition 3.4.** Define an equivalence relation $\sim$ on the set of vertices of $G_{T,\gamma}$ as follows: Vertices of $G_{T,\gamma}$ are equivalent if they correspond to the same marked point on the original polygon $T'$, based on how quadrilaterals from the polygon become tiles in $G_{T,\gamma}$. Let the equivalence class of a vertex $v$ be $[v]$.

The location of equivalent vertices follows this specific pattern: $v \sim v'$ if one can start at $v$ and reach $v'$ by a sequence of northwest-southeast knight's moves (i.e. we are allowed to make the “knight’s move” in only 4 directions (not 8): left 1 and up 2, left 2 and up 1, right 1 and down 2, or right 2 and down 1).

**Remark 3.5.** Note that in $G_{T,\gamma}$, any number of vertices can be in an equivalence class, but at most two edges have the same label (because any edge in the triangulation is an edge of either 1 or 2 quadrilaterals, and $\gamma$ cannot cross the same diagonal more than once).

**Definition 3.6.** A tile $\bar{S}$ in $G_{T,\gamma}$ will be called a corner if it is incident to two other tiles, one of which is left or right of $\bar{S}$, and one of which is above or below $\bar{S}$.

**Definition 3.7.** A diagonal $e$ in $D(\gamma)$ will be called balanced if a pair of opposite sides of quadrilateral $Q_{\tau_e}$ consists of boundary segments of $T'$, and will be called imbalanced otherwise.

**Definition 3.8.** A subgraph $H$ of a bipartite graph $G$ will be called an elementary subgraph if $H$ contains every vertex of $G$, and every edge of $H$ is used in some perfect matching of $H$. Equivalently, $H$ is an elementary subgraph if it is the union of some set of perfect matchings of $G$.
**Example 3.9.** To illustrate this vocabulary, we will use the triangulation and snake graph from Figure 2 as an example. The set $D(\gamma) = \{2, 3, 4, 5, 6\}$, and $T'$ is the graph shown in Figure 3. The vertices of $G_{T,\gamma}$ in Figure 2 are labeled with lowercase letters to naturally correspond to the vertices of $T'$, labeled in uppercase.

<figure><img src="image_3.png" /><figcaption>Fig. 3: $T'$ for the example in Figure 2</figcaption></figure>

The equivalence class $[a']$ is $\{a, a', a''\}$. Observe the northwest-southeast knight's moves between these vertices of $G_{T,\gamma}$, and notice that this equivalence class corresponds to vertex $A$ of $T'$.

Also, $E_{[a']} = \{1, 2, 3, 4, 7\}$, and diagonals($A$) = $\{2, 3, 4\}$.

Note that in $T'$, the diagonal connecting vertices $B$ and $E$ is labeled “5”. Correspondingly, in $G_{T,\gamma}$, the edges $\{b, e\}$ and $\{b', e'\}$ are both labeled “5”. Moreover, $Q_{\tau_5} = (7, 4, 10, 6)$. The diagonal “5” is balanced, and the diagonal “3” is imbalanced. Note that $G_{T,\gamma}$ has 1 corner - the second tile.

To construct $P(G_{T,\gamma})$, we associate a characteristic vector in $\mathbb{R}^{15}$ to every perfect matching of $G_{T,\gamma}$, and find the convex hull of all these vectors. For example, the matching below gives the vector $(1, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0)$.

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

Our first proposition describes the affine hull of $P(G_{T,\gamma})$, the “Newton polytope of the numerator” of a cluster variable. It follows from carefully examining how features of the triangulation correspond to features of the snake graph, along with a classical result (see [5, 16]) on bipartite graphs and associated polytopes, along with the formula from Proposition 2.3 and some linear algebra.
**Proposition 3.10.** For any diagonal $\gamma$, the affine hull of the polytope $P(G_{T,\gamma})$ can be found from the snake graph $G_{T,\gamma}$ by writing the following equations:

$$ (i) \quad x_e = 0 \text{ for each edge } e \in T \text{ that does not appear in } G_{T,\gamma} $$

$$ (ii) \quad \sum_{e \in E_{[v]}} x_e = |[v]| \text{ for each vertex equivalence class } [v] \text{ of } G_{T,\gamma} $$

Using the triangulation $T$ directly, the equivalent equations are

$$ (iii) \quad x_e = 0 \text{ for each edge } e \text{ of } T \setminus T' $$

$$ (iv) \quad \sum_{e \ni w} x_e = |\text{diagonals}(w)| \text{ for each vertex } w \text{ of } T' $$

The equations defining the affine hull here (either (i)-(ii) or (iii)-(iv)) are linearly independent, and thus are a minimal description of the affine hull. There are $2n + 3 - |D(\gamma)|$ equations in this description.

**Corollary 3.11.** $\dim N(T, \gamma) = \dim P(G_{T,\gamma}) = |D(\gamma)|$.

We use a classical result from the literature on bipartite graphs and associated polytopes [1] to obtain our first main result: a description of the face lattice of $N(T, \gamma)$.

**Theorem 3.12.** The face lattice of $N(T, \gamma)$ (and of $P(G_{T,\gamma})$) is isomorphic to the lattice of all elementary subgraphs of $G_{T,\gamma}$, ordered by inclusion.

**Corollary 3.13.** The following are in one-to-one correspondence:

(i) *Laurent monomials in the $T$-expansion of $x_\gamma$*

(ii) *perfect matchings of $G_{T,\gamma}$*

(iii) *vertices of $N(T, \gamma)$*

**Example 3.14.** We will illustrate Theorem 3.12 using a small example. Let $T$ be a triangulation of a pentagon, with $\gamma$ a diagonal that crosses both diagonals of $T$. Then $G_{T,\gamma}$ consists of two boxes, and the face lattice of $N(T, \gamma)$ is isomorphic to the lattice of elementary subgraphs of $G_{T,\gamma}$ shown in Figure 4.

In this example, the dimension of $N(T, \gamma)$ is $|D(\gamma)| = 2$, and $N(T, \gamma)$ is a triangle. Also note that the length of every maximal chain in this lattice is 3.

The lattices described in Theorem 3.12 are graded: the rank of a face is 1 more than its dimension, and the rank of an elementary subgraph is 1 more than the number of chordless cycles it contains. So the $d$-faces of $N(T, \gamma)$ are in bijection with elementary subgraphs of $G_{T,\gamma}$ with exactly $d$ chordless cycles.

In particular, let $P(i)$ be the perfect matching of $G_{T,\gamma}$ that corresponds to vertex $i$ of the polytope. Given a set of vertices $(i_1, \dots, i_r)$ that make up a face, the corresponding elementary subgraph is obtained by superimposing $P(i_1), \dots, P(i_r)$. Conversely, given an elementary subgraph $H$, if the set of all perfect matchings of $G_{T,\gamma}$ that lie entirely on $H$ is $P(i_1), \dots, P(i_r)$, then $(i_1, \dots, i_r)$ is the set of vertices making up the corresponding face. Also, the facets of $N(T, \gamma)$ are the $(n-1)$-faces, so they can be found by finding the elementary subgraphs of $G_{T,\gamma}$ containing $n-1$ chordless cycles. Doing this, we obtain the following proposition that relates the facets of $P(G_{T,\gamma})$ to the snake graph.
<figure><img src="image_5.png" /><figcaption>**Fig. 4:** Lattice of Elementary Subgraphs of $G_{T,\gamma}$</figcaption></figure>

**Proposition 3.15.** For any diagonal $\gamma$, the facets of the polytope $P(G_{T,\gamma})$ can be found from the snake graph $G_{T,\gamma}$ by writing the following inequalities:

(i) $x_e \ge 0$ for each $e \in G_{T,\gamma}$ such that $e$ is an interior edge of $G_{T,\gamma}$.

(ii) $x_e \ge 0$ for each pair of opposite exterior edges $\{e, f\}$ of $G_{T,\gamma}$ such that at least one of the two edges has a label $e$ that is unique in $G_{T,\gamma}$. (see figure below)

(iii) $x_a + x_b + x_c \le 2$ for each pair of opposite exterior edges $\{e, f\}$ of $G_{T,\gamma}$ that includes no unique labels, where a, b and c are the labels of edges shown in the figure below.

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

**Corollary 3.16.** If $|D(\gamma)| \ge 2$, the number of facets of $N(T, \gamma)$ (or $P(G_{T,\gamma})$) is $2d - 1 - t$, where $t$ is the number of corners in the snake graph, or equivalently, the number of imbalanced diagonals in $T'$. (If $|D(\gamma)| = 1$, the polytope is a line segment, so it has 2 facets that are the endpoints.)

Combining Proposition 3.10, Proposition 3.15, and Remark 3.3, we obtain our second main result: a description of the affine hull and facets of $N(T, \gamma)$ that can be read directly from the triangulation.

**Theorem 3.17.** For any diagonal $\gamma$, the polytope $N(T, \gamma)$ can be found directly from $T$ as follows: Affine hull equations:

(i) For each edge $e$ of $T \setminus T'$, write $x_e = 0$.

(ii) For each vertex $w \in T'$, write $\sum_{e \ni w} x_e = 1$ if $w \in \gamma$, or write $\sum_{e \ni w} x_e = 0$ if $w \notin \gamma$.
Facet-defining inequalities:

(iii) For every boundary segment $e \in T'$ not incident to $\gamma$, write $x_e \ge 0$.

(iv) For every pair of boundary segments $\{b, c\}$ of $T'$ that are opposite sides of $Q_{\tau_a}$, where $a \in D(\gamma)$ is a balanced diagonal, let the other pair of opposite sides of $Q_{\tau_a}$ be $\{e, f\}$. Exactly one of these three cases will hold for each pair $\{e, f\}$:

- If $\{e, f\} \subset \{\tau_{i_2}, \dots, \tau_{i_{d-1}}\}$, write the inequality $x_a + x_b + x_c \le 1$.

- If one of $\{e, f\}$ (say $e$) is a boundary segment of $T'$, write $x_e \ge 0$.

- Otherwise, write $x_e \ge -1$, where $e$ is diagonal $\tau_{i_1}$ or $\tau_{i_d}$.

**Example 3.18.** Using the same example as in section 1, we will illustrate Theorem 3.17.

• (i): Since edges 14 and 15 of $T$ do not appear in $T'$, we get $x_{14} = 0$ and $x_{15} = 0$.

• (ii): The other equations defining the affine hull of $N(T, \gamma)$ come from each vertex of $T'$ and whether they are incident to $\gamma$. For example, the edges incident to vertex $A$ are $\{1, 2, 3, 4, 7\}$, and $A$ is not incident to $\gamma$, so we get the equation $x_1 + x_2 + x_3 + x_4 + x_7 = 0$.

• (iii): Edges 7, 10, 11, and 12 are boundary segments of the triangulated polygon $T'$ that are not incident to $\gamma$, so we get $x_7 \ge 0$, $x_{10} \ge 0$, $x_{11} \ge 0$, $x_{12} \ge 0$.

• (iv): The pairs of boundary segments of $T'$ that are opposite sides of $Q_{\tau_a}$, where $a$ is a balanced diagonal in $D(\gamma)$, are $\{1, 12\}$, $\{7, 11\}$, $\{7, 10\}$, and $\{8, 10\}$. The other pairs of opposite sides of each quadrilateral are, respectively, $\{3, 13\}$, $\{3, 5\}$, $\{4, 6\}$, and $\{5, 9\}$. Since $\{\tau_{i_1}, \tau_{i_2}, \dots, \tau_{i_{d-1}}, \tau_{i_d}\} = \{2, 3, 4, 5, 6\}$, these pairs fall into the following cases:

- Both of $\{3, 5\}$ are in $\{\tau_{i_2}, \dots, \tau_{i_{d-1}}\} = \{3, 4, 5\}$. They are sides of $Q_{\tau_4}$, whose other two sides are 7 and 11. This gives $x_4 + x_7 + x_{11} \le 1$.

- Edge 13 is a boundary segment, so $\{3, 13\}$ gives $x_{13} \ge 0$. Similarly, $\{5, 9\}$ gives $x_9 \ge 0$.

- Edges $\{4, 6\}$ are not both in $\{3, 4, 5\}$, nor is either a boundary segment, so we get $x_6 \ge -1$.

Putting this all together, the affine hull and facets of $N(T, \gamma)$ are given by

affine hull: $x_{14} = 0, x_{15} = 0$

$A: x_1 + x_2 + x_3 + x_4 + x_7 = 0$

$C: x_8 + x_9 = 1$

$E: x_4 + x_5 + x_{10} + x_{11} = 0$

$G: x_2 + x_{12} + x_{13} = 0$

facets: $x_7 \ge 0, x_{10} \ge 0, x_{11} \ge 0, x_{12} \ge 0,$

$x_{13} \ge 0, x_9 \ge 0, x_6 \ge -1, x_4 + x_7 + x_{11} \le 1$

$B: x_5 + x_6 + x_7 + x_8 = 0$

$D: x_6 + x_9 + x_{10} = 0$

$F: x_3 + x_{11} + x_{12} = 0$

$H: x_1 + x_{13} = 1$

Note that Corollary 3.16 confirms that we have found all the facets $(2d-1-t=2(5)-1-1=8$ facets).
# 4 Other Remarks and Conjectures

Empirical evidence suggests that the polytope $N(T, \gamma)$ contains no lattice points in its relative interior.
The author hopes to prove this in a future paper.

If all the frozen variables {$x_{n+1}, ..., x_{2n+3}$} (i.e. boundary segments of the polygon) are set equal to 1,
the Newton polytope $N(T, \gamma)$ is less elegant - there is a collapsing of monomials in the cluster expansion,
and not every monomial corresponds to a vertex.

The construction of cluster algebras from triangulations of a polygon may be generalized to construct
cluster algebras from triangulations of an arbitrary surface with marked points ([6, 7, 8, 13, 9]). In this
setting, there is a generalization of the Laurent expansion formula using perfect matchings of snake graphs
([17, 18, 19]). Many of the results of this paper do not seem easily generalized to the case of a surface
more general than a polygon. For example, our result on the isomorphism of lattices does not hold for
an annulus with marked points on the boundaries. For many surfaces other than a polygon, our results
concerning the facets are not valid, and our affine hull description in Theorem 3.17(i)-(ii) seems only
partially complete, in that the theorem seems to give some of the affine hull equations, but not necessarily
all of them. Soon, we hope to have a complete affine hull and facet description for cluster variables from
more general surfaces.

# References

[1] L. Billera, A. Sarangarajan, The combinatorics of permutation polytopes. Formal power series and algebraic combinatorics (New Brunswick, NJ, 1994), 1-23, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 24, Amer. Math. Soc., Providence, RI, 1996.

[2] G. Carroll, G. Price, Two new combinatorial models for the Ptolemy recurrence, unpub., 2003.

[3] G. Cerulli Irelli, Cluster Algebras of type $A_2^{(1)}$. Algebr. Repr. Theory 15 (2012), no. 5, 977-1021.

[4] G. Dupont, H. Thomas, Atomic bases in cluster algebras of types $A$ and $\tilde{A}$. Proc. Lond. Math. Soc. (3) 107 (2013), no. 4, 825-850.

[5] J. Edmonds, Paths, trees, and flowers. Canad. J. Math. 17 1965 449-467.

[6] V. Fock and A. Goncharov, Moduli spaces of local systems and higher Teichmüller theory. Publ. Math. Inst. Hautes Études Sci. No. 103 (2006), 1-211.

[7] V. Fock and A. Goncharov, Cluster ensembles, quantization and the dilogarithm. Ann. Sci. Éc. Norm. Supér. (4) 42 (2009), no. 6, 865-930.

[8] V. Fock and A. Goncharov, Dual Teichmüller and lamination spaces. Handbook of Teichmüller theory. Vol. I, 647-684, IRMA Lect. Math. Theor. Phys., 11, Eur. Math. Soc., Zürich, 2007.

[9] S. Fomin, M. Shapiro, D Thurston, Cluster algebras and triangulated surfaces I. Cluster complexes. Acta Math. 201 (2008), no. 1, 83-146.
[10] S. Fomin, A Zelevinsky, Cluster algebras I: Foundations. J. Amer. Math. Soc. 15 (2002), 497-529.

[11] S. Fomin, A. Zelevinsky, Cluster algebras II. Finite type classification. Invent. Math. 154 (2003), no. 1, 63-121.

[12] S. Fomin, A. Zelevinsky, Cluster algebras IV: Coefficients. Compos. Math. 143 (2007), no.1, 112-64.

[13] M. Gekhtman, M. Shapiro, A. Vainshtein, Cluster algebras and Weil-Petersson forms. Duke Math. J. 127 (2005), no. 2, 291-311.

[14] Ewgenij Gawrilow and Michael Joswig. polymake: a framework for analyzing convex polytopes. Polytopes-combinatorics and computation (Oberwolfach, 1997), 43-73, DMV Sem., 29, Birkhäuser, Basel, 2000.

[15] A. Kalman, Newton polytopes of cluster variables of type $A_n$, arXiv:1310.0555

[16] L. Lovasz, M. Plummer, Matching theory. North-Holland Mathematics Studies, 121. Annals of Discrete Math., 29. North-Holland Publishing Co., Amsterdam; Akadémiai Kiadó (Publishing House of the Hungarian Academy of Sciences), Budapest, 1986. xxvii+544 pp. ISBN: 0-444-87916-1

[17] G. Musiker, R. Schiffler, Cluster expansion formulas and perfect matchings, J. Algebraic Combin. 32 (2010), no. 2, 187-209.

[18] G. Musiker, R. Schiffler, L. Williams, Positivity for cluster algebras from surfaces. Adv. Math. 227 (2011), no. 6, 2241-2308.

[19] G. Musiker, R. Schiffler, L. Williams, Bases for cluster algebras from surfaces. Compos. Math. 149 (2013), no. 2, 217-263.

[20] J. Propp, The combinatorics of frieze patterns and Markoff numbers, arXiv:math.CO/0511633

[21] A. Postnikov, D. Speyer, L. Williams, Matching polytopes, toric geometry, and the totally non-negative Grassmannian. J. Algebraic Combin. 30 (2009), no. 2, 173-191.

[22] R. Schiffler, A cluster expansion formula ($A_n$ case), Electron. J. Combin. 15 (2008), no. 1, Research paper 64, 9 pp.

[23] R. Schiffler, On cluster algebras arising from unpunctured surfaces. II. Adv. Math. 223 (2010), no. 6, 1885-1923.

[24] R. Schiffler, H. Thomas, On cluster algebras arising from unpunctured surfaces, Int. Math. Res. Not. IMRN 2009, no. 17, 3160-3189.

[25] P. Sherman, A. Zelevinsky, Positivity and canonical bases in rank 2 cluster algebras of finite and affine types. Mosc. Math. J. 4 (2004), no. 4, 947-974, 982.

[26] G. Ziegler, Lectures on polytopes. Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995. x+370 pp. ISBN: 0-387-94365-X