# A combinatorial model for exceptional sequences in type A

Alexander Garver, Jacob P. Matherne

► To cite this version:

Alexander Garver, Jacob P. Matherne. A combinatorial model for exceptional sequences in type A. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.393-404, 10.46298/dmtcs.2513 . hal-01337808

HAL Id: hal-01337808

https://hal.science/hal-01337808

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# A combinatorial model for exceptional sequences in type A

Alexander Garver$^{1}$† and Jacob P. Matherne$^{2}$‡

**Abstract.** Exceptional sequences are certain ordered sequences of quiver representations. We use noncrossing edge-labeled trees in a disk with boundary vertices (expanding on T. Araya's work) to classify exceptional sequences of representations of $\mathcal{Q}$, the linearly ordered quiver with $n$ vertices. We also show how to use variations of this model to classify $\mathcal{c}$-matrices of $\mathcal{Q}$, to interpret exceptional sequences as linear extensions, and to give a simple bijection between exceptional sequences and certain chains in the lattice of noncrossing partitions. In the case of $\mathcal{c}$-matrices, we also give an interpretation of $\mathcal{c}$-matrix mutation in terms of our noncrossing trees with directed edges.

**Résumé.** Les suites exceptionnelles sont certaines suites ordonnées de représentations de carquois. Nous utilisons des arbres aux arêtes étiquetés et aux sommets dans le bord d'un disque (expansion sur le travail de T. Araya) pour classifier les suites exceptionnelles de représentations du carquois linéairement ordonné à n sommets. Nous exploitons des variations de ce modèle pour classifier les $\mathcal{c}$-matrices dudit carquois, pour interpréter les suites exceptionnelles comme des extensions linéaires, et pour donner une bijection élémentaire entre les suites exceptionnelles et certaines chaînes dans le réseau des partitions sans croisement. Dans le cas des $\mathcal{c}$-matrices, nous donnons également une interprétation de la mutation des $\mathcal{c}$-matrices en termes des arbres sans croisement aux arêtes orientés.

**Keywords:** quiver mutation, exceptional sequences, $\mathcal{c}$-matrices, linear extensions

## 1 Introduction

Exceptional sequences are certain ordered sequences of quiver representations introduced in [GR87] to study exceptional vector bundles on $\mathbb{P}^2$. Maximal such sequences called complete exceptional sequences also have connections with combinatorics as they are in bijection with maximal chains in the lattice of noncrossing partitions by the work of [IT09] and [HK13]. More recently, complete exceptional sequences were shown to be intrinsically related to acyclic cluster algebras with principal coefficients via the work of Speyer and Thomas [ST13]. They appear as certain orderings of the $\mathcal{c}$-vectors of a $\mathcal{c}$-matrix in such a cluster algebra.

<footnote>$^{1}$School of Mathematics, University of Minnesota, USA</footnote>

<footnote>$^{2}$Department of Mathematics, Louisiana State University, USA</footnote>

<footnote>†Email: garver0102@math.umn.edu. This author was supported by a Research Training Group, RTG grant DMS-1148634.</footnote>

<footnote>‡Email: jmath34@tigers.lsu.edu. This author was supported by a Graduate Assistance in Areas of National Need fellowship, GAANN grant P200A120001.</footnote>
We take a combinatorial approach to the study of exceptional sequences. In [Ara13], Araya establishes a bijection between the set of complete exceptional collections in type $\mathbb{A}$ and the collection of certain chord diagrams called noncrossing spanning trees. It is this simple combinatorial model that serves as the vehicle to our results. Proofs of all of our results will appear in [GM14].

In Section 3, we decorate Araya’s diagrams with edge-labelings and oriented edges so that they can keep track of both the ordering of the representations in a complete exceptional sequence as well as the signs of the rows in the **c-matrix** it came from. While Araya’s diagrams classify complete exceptional collections, we show that the new decorated diagrams classify more complicated objects called exceptional sequences (Theorem 3). In this language, we give a rule for mutation of oriented diagrams arising from **c-matrices** in Section 4. We remark that our work is connected to that of Goulden and Yong [GY02] who used edge-labeled noncrossing spanning trees in a disk to study factorizations of the long cycle $(1, 2, \dots, n+1) \in S_{n+1}$ by a collection of transpositions.

The work of Speyer and Thomas (see [ST13]) allows complete exceptional sequences to be obtained from **c-matrices**. In $[ONAS^+13]$, the number of complete exceptional sequences in type $A_n$ is given, and there are more of these than there are **c-matrices**. Thus, it is natural to ask exactly which **c-matrices** appear as Araya’s diagrams. We give an answer to this question in Section 5 (Theorem 5).

In Section 6 we ask how many complete exceptional sequences can be formed using the representations in a complete exceptional collection. We interpret this number as the number of linear extensions of the poset determined by the chord diagram of the complete exceptional collection. This also gives an interpretation of complete exceptional sequences as linear extensions.

In Section 7, we give several applications of the theory in type $\mathbb{A}$, including combinatorial proofs that two reddening sequences produce isomorphic ice quivers (see [Kel12] for a general proof in all types using deep category-theoretic techniques) and that there is a bijection between exceptional sequences and certain chains in the lattice of noncrossing partitions.

## 2 Exceptional Sequences

We begin by defining quivers and exchange matrices, which serve as the starting point in our study of exceptional sequences.

### 2.1 Quiver Mutation

A **quiver** $Q$ is a directed graph without loops or 2-cycles. In other words, $Q$ is a 4-tuple $(Q_0, Q_1, s, t)$, where $Q_0 = [m] := \{1, 2, \dots, m\}$ is a set of **vertices**, $Q_1$ is a set of **arrows**, and two functions $s, t$: $Q_1 \to Q_0$ defined so that for every $\alpha \in Q_1$, we have $s(\alpha) \xrightarrow{\alpha} t(\alpha)$. An **ice quiver** is a pair $(Q, F)$ with $Q$ a quiver and $F \subset Q_0$ **frozen vertices** with the additional restriction that any $i, j \in F$ have no arrows of $Q$ connecting them. We refer to the elements of $Q_0\setminus F$ as **mutable vertices**. By convention, we assume $Q_0\setminus F = [n]$ and $F = [n+1, m] := \{n+1, n+2, \dots, m\}$. Any quiver $Q$ can be regarded as an ice quiver by setting $Q = (Q, \emptyset)$.

The **mutation** of an ice quiver $(Q, F)$ at mutable vertex $k$, denoted $\mu_k$, produces a new ice quiver $(\mu_k Q, F)$ by the three step process:

(1) For every 2-path $i \to k \to j$ in $Q$, adjoin a new arrow $i \to j$.

(2) Reverse the direction of all arrows incident to $k$ in $Q$.

(3) Delete any 2-cycles created during the first two steps.
We show an example of mutation below depicting the mutable (resp. frozen) vertices in black (resp. blue).

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

The information of an ice quiver can be equivalently described by its (skew-symmetric) **exchange matrix**. Given $(Q, F)$, we define $B = B_{(Q,F)} = (b_{ij}) \in \mathbb{Z}^{n \times m} := \{n \times m \text{ integer matrices}\}$ by $b_{ij} := \#\{i \xrightarrow{\alpha} j \in Q_1\} - \#\{j \xrightarrow{\alpha} i \in Q_1\}$. Furthermore, ice quiver mutation can equivalently be defined as **matrix mutation** of the corresponding exchange matrix. Given an exchange matrix $B \in \mathbb{Z}^{n \times m}$, the **mutation** of $B$ at $k \in [n]$, also denoted $\mu_k$, produces a new exchange matrix $\mu_k(B) = (b'_{ij})$ with entries

$$b'_{ij} := \begin{cases} -b_{ij} & : \text{ if } i = k \text{ or } j = k \\ b_{ij} + \frac{|b_{ik}|b_{kj} + b_{ik}|b_{kj}|}{2} & : \text{ otherwise.} \end{cases}$$

For example, the mutation of the ice quiver above (here $m = 4$ and $n = 3$) translates into the following matrix mutation. Note that mutation of matrices or ice quivers is an involution (i.e. $\mu_k \mu_k(B) = B$).

$$B_{(Q,F)} = \left[ \begin{array}{ccc|c} 0 & 2 & 0 & 0 \\ -2 & 0 & 1 & 0 \\ 0 & -1 & 0 & -1 \end{array} \right] \xrightarrow{\mu_2} \left[ \begin{array}{ccc|c} 0 & -2 & 2 & 0 \\ 2 & 0 & -1 & 0 \\ -2 & 1 & 0 & -1 \end{array} \right] = B_{(\mu_2 Q, F)}.$$

Given a quiver $Q$, we define its **framed** (resp. **coframed**) quiver to be the ice quiver $\tilde{Q}$ (resp. $\tilde{Q}$) where $\tilde{Q}_0 (= \tilde{Q}_0) := Q_0 \sqcup [n+1, 2n]$, $F = [n+1, 2n]$, and $\tilde{Q}_1 := Q_1 \sqcup \{i \to n+i : i \in [n]\}$ (resp. $\tilde{Q}_1 := Q_1 \sqcup \{n+i \to i : i \in [n]\}$). Now given $\tilde{Q}$ we define the **exchange tree** of $\tilde{Q}$, denoted $ET(\tilde{Q})$, to be the (a priori infinite) graph whose vertices are quivers obtained from $\tilde{Q}$ by a finite sequence of mutations and with two vertices connected by an edge if and only if the corresponding quivers are obtained from each other by a single mutation. Similarly, define the **exchange graph** of $\tilde{Q}$, denoted $EG(\tilde{Q})$, to be the quotient of $ET(\tilde{Q})$ where two vertices are identified if and only if there is a **frozen isomorphism** of the corresponding quivers (i.e. an isomorphism that fixes the frozen vertices). Such an isomorphism is equivalent to a simultaneous permutation of the rows and the first $n$ columns of one of the corresponding exchange matrices.

Given $\tilde{Q}$, we define the **c-matrix** $C(n) = C_R(n)$ (resp. $C = C_R$) of $R \in ET(\tilde{Q})$ (resp. $R \in EG(\tilde{Q})$) to be the submatrix of $B_R$ where $C(n) := (b_{ij})_{i \in [n], j \in [n+1, 2n]}$ (resp. $C := (b_{ij})_{i \in [n], j \in [n+1, 2n]}$). We let **c-mat**($Q$) := {$C_R : R \in EG(\tilde{Q})$}. By definition, $B_R$ (resp. $C$) is only defined up to simultaneous permutations of its rows and its first $n$ columns (resp. up to permutations of its rows) for any $R \in EG(\tilde{Q})$.

A row vector of a **c-matrix**, $\vec{c}$, is known as a **c-vector**. The celebrated theorem of Derksen, Weyman, and Zelevinsky [DWZ10, Theorem 1.7], known as the Sign-Coherence of **c-vectors**, states that for any $R \in ET(\tilde{Q})$ and $i \in [n]$ the **c-vector** $\vec{c}_i$ is a nonzero element of $\mathbb{Z}_{\ge 0}^n$ or $\mathbb{Z}_{\le 0}^n$. Thus we say a **c-vector** is either **positive** or **negative**.

For the purposes of this paper, we will only be concerned with the linearly ordered $\mathbb{A}_n$ quiver $Q$ shown
below with its framed quiver $\hat{Q}$.

$$Q = 1 \leftarrow 2 \leftarrow \dots \leftarrow n-1 \leftarrow n \quad \hat{Q} = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.5, every node/.style={scale=0.8}] \node (n1) at (0,0) {$n+1$}; \node (n2) at (0,2) {$n+2$}; \node (n3) at (0,4) {$2n-1$}; \node (n4) at (0,6) {$2n$}; \draw[->] (n1) -- (n2); \draw[->] (n2) -- (n3); \draw[->] (n3) -- (n4); \node[above] at (n1) {$1$}; \node[above] at (n2) {$2$}; \node[above] at (n3) {$n-1$}; \node[above] at (n4) {$n$}; \node[left] at (n1) {$1$}; \node[right] at (n2) {$2$}; \node[right] at (n3) {$n-1$}; \node[right] at (n4) {$n$}; \end{tikzpicture}$$

## 2.2 Representations of quivers

A **representation** $V = ((V_i)_{i \in Q_0}, (\varphi_\alpha)_{\alpha \in Q_1})$ of a quiver $Q$ is an assignment of a $k$-vector space $V_i$ to each vertex $i$ and a $k$-linear map $\varphi_\alpha : V_{s(\alpha)} \to V_{t(\alpha)}$ to each arrow $\alpha$ where $k$ is an algebraically closed field. The **dimension vector** of $V$ is the vector $\dim(V) := (\dim_{k} V_i)_{i \in Q_0}$. Here is an example of a representation, with $\dim(V) = (3, 3, 2)$, of the **mutable part** of the quiver depicted in Section 2.1.

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

Let $V = ((V_i)_{i \in Q_0}, (\varphi_\alpha)_{\alpha \in Q_1})$ and $W = ((W_i)_{i \in Q_0}, (\varrho_\alpha)_{\alpha \in Q_1})$ be two representations of a quiver $Q$. A **morphism** $\theta: V \to W$ consists of a collection of linear maps $\theta_i: V_i \to W_i$ that are compatible with each of the linear maps in $V$ and $W$. That is, for each arrow $\alpha \in Q_1$, we have $\theta_{t(\alpha)} \circ \varphi_{\alpha} = \varrho_{\alpha} \circ \theta_{s(\alpha)}$. An **isomorphism** of quiver representations is a morphism $\theta: V \to W$ where $\theta_i$ is a $k$-vector space isomorphism for all $i \in Q_0$. We define $V \oplus W := ((V_i \oplus W_i)_{i \in Q_0}, (\varphi_\alpha \oplus \varrho_\alpha)_{\alpha \in Q_1})$ to be the **direct sum** of $V$ and $W$. We say that a nonzero representation $V$ is **indecomposable** if it is not isomorphic to a direct sum of two nonzero representations.

For the linearly ordered $\mathbb{A}_n$ quiver, it is a standard exercise to show that its indecomposable representations up to isomorphism are exactly the representations $X_{i,j}$ with $0 \le i < j \le n$ defined as

$$X_{i,j} := \begin{array}{ccccccc} 1 & & & & & & \\ & 0 & \leftarrow & \dots & \leftarrow & 0 & \leftarrow & k \\ & & & & & & \leftarrow & \dots \\ & & & & & & \leftarrow & 0 & \leftarrow & \dots & \leftarrow & 0. \end{array}$$

We remark that representations of $Q$ can equivalently be regarded as modules over the **path algebra** $kQ$. As such, one can define $\mathrm{Ext}^s(V, W)$ ($s \ge 0$) and $\mathrm{Hom}(V, W)$ for any representations $V$ and $W$. We refer the reader to [ASS06] for more details on representations of quivers.

An **exceptional sequence** $\xi = (V_1, \dots, V_k)$ ($k \le n := \#Q_0$) is an ordered list of **exceptional representations** $V_j$ of $Q$ (i.e. $V_j$ is indecomposable and $\mathrm{Ext}^s(V_j, V_j) = 0$ for all $s \ge 1$) satisfying $\mathrm{Hom}(V_j, V_i) = 0$ and $\mathrm{Ext}^s(V_j, V_i) = 0$ if $i < j$ for all $s \ge 1$. We define an **exceptional collection** $\bar{\xi} = \{V_1, \dots, V_k\}$ to be a **set** of exceptional representations $V_j$ of $Q$ that can be ordered in such a way that they define an exceptional sequence. When $k = n$, we say $\xi$ (resp. $\bar{\xi}$) is a **complete exceptional sequence** (CES) (resp. **complete exceptional collection** (CEC)). For the linearly ordered quiver, a representation is exceptional if and only if it is indecomposable.

The following result of Speyer and Thomas gives a beautiful connection between $c$-matrices of an acyclic quiver $Q$ and CESs. It serves as motivation for our work. Before stating it, we remark that any $c$-vector $\vec{c}$ of an acyclic quiver $Q$ satisfies $\vec{c} = \pm \dim(V)$ for some indecomposable representation of $Q$ [Cha12].
**Theorem 1 ([ST13)** Let $C \in \mathbf{c-mat}(Q)$, let $\{\vec{c_i}\}_{i \in [n]}$ denote the $\mathbf{c}$-vectors of $C$, and let $\vec{c_i} = \pm \dim(V_i)$ for some indecomposable representation of $Q$. There exists a permutation $\sigma \in S_n$ such that $(V_{\sigma(1)}, \dots, V_{\sigma(n)})$ is a CES with the property that if there exist positive $\mathbf{c}$-vectors in $C$, then there exists $k \in [n]$ such that $\vec{c}_{\sigma(i)}$ is positive if and only if $i \in [k, n]$, and $\text{Hom}_{kQ}(V_i, V_j) = 0$ if $\vec{c_i}, \vec{c_j}$ have the same sign. Conversely, any set of $n$ vectors having these properties defines a $\mathbf{c}$-matrix whose rows are $\{\vec{c_i}\}_{i \in [n]}$.

### 3 Chord diagrams and exceptional sequences

We henceforth fix $n \in \mathbb{N}$ and use $Q$ to denote the linearly ordered $\mathbb{A}_n$ quiver.

A **chord diagram** $d = \{c(i_\ell, j_\ell)\}_{\ell \in [k]}$ with $k \in [n]$ is a graph embedded in a disk with $n+1$ vertices, called **marked points**, on the boundary of the disk. The marked points are labeled 0, 1, ..., $n$ counter-clockwise starting from the top of the disk. We let $c(i, j)$ denote the **chord** connecting the marked points labeled $i$ and $j$. Furthermore, we require that the chords are pairwise non-intersecting in the interior of the disk and that the underlying graph of $d$ is a forest. We similarly define a **labeled** (resp. **oriented**) chord diagram, denoted $d(k) = \{(c(i_\ell, j_\ell), s_\ell)\}_{\ell \in [k]}$ (resp. $\vec{d} = \{\vec{c}(i_\ell, j_\ell)\}_{\ell \in [k]}$), to be a chord diagram each of whose chords are labeled by an integer $s_\ell \in [k]$ bijectively (resp. whose chords $\vec{c}(i_\ell, j_\ell)$ are oriented from $i_\ell$ to $j_\ell$). We give examples of each notion of chord diagram of type $\mathbb{A}_3$ below.

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

**Theorem 2 ([Ara13]** Let $\bar{\mathcal{E}} := \{\text{complete exceptional collections}\}$, $\mathcal{D} := \{\text{diagrams } d = \{c(i_\ell, j_\ell)\}_{\ell \in [n]}\}$. The map $\bar{\mathcal{E}} \to \mathcal{D}$ defined by $\bar{\xi} = \{X_{i_1, j_1}, \dots, X_{i_n, j_n}\} \mapsto \{c(i_\ell, j_\ell)\}_{\ell \in [n]}$ is a bijection.

Let $d(k)$ be a labeled diagram, let $i$ be any marked point, and let $((c(i, j_1), s_1), \dots, (c(i, j_{j_r}), s_r))$ be the complete list of chords in $d(k)$ involving $i$ ordered so that chords appearing later in the list are clockwise from those earlier in the list in $d(k)$. We say the chord-labeling of $d(k)$ is **good** if for each marked point $i$ one has $s_1 < \dots < s_r$. The labeling of the diagram in the previous example is not good.

We now state our first main result. Let $\mathcal{D}(k)$ denote the set of diagrams with $k$ chords and with good labelings and let $\mathcal{E}(k) := \{\text{exceptional sequences } \xi = (V_1, \dots, V_k)\}$.

**Theorem 3** Let $k \in [n]$. One has a bijection $\mathcal{E}(k) \to \mathcal{D}(k)$ given by

$$ \xi = (X_{i_1, j_1}, \dots, X_{i_k, j_k}) \mapsto \{(c(i_\ell, j_\ell), k+1-\ell)\}_{\ell \in [k]}. $$

**Proof Sketch:** A sequence of representations $(V_1, \dots, V_k)$ is exceptional if and only if $(V_i, V_j)$ is an **exceptional pair** (i.e. an exceptional sequence of length 2) for all $i, j \in [k]$ where $i < j$. It can be shown that $X_{i_\ell, j_\ell}$ and $X_{i_{\ell'}, j_{\ell'}}$ determine exactly one exceptional sequence if and only if the chords $c(i_\ell, j_\ell)$ and $c(i_{\ell'}, j_{\ell'})$ intersect at exactly one marked point (this fact can be deduced from [Ara13, Lemma 3.2]). If $i_\ell = i_{\ell'}$, one shows that the only exceptional sequence determined by $X_{i_\ell, j_\ell}$ and $X_{i_{\ell'}, j_{\ell'}}$ is either $(X_{i_\ell, j_\ell}, X_{i_{\ell'}, j_{\ell'}})$ if $j_\ell < j_{\ell'}$ or $(X_{i_\ell, j_\ell}, X_{i_{\ell'}, j_{\ell'}})$ if $j_{\ell'} < j_\ell$. If $j_\ell < j_{\ell'}$ (resp. $j_{\ell'} < j_\ell$), then $c(i_\ell, j_\ell)$ (resp. $c(i_\ell, j_{\ell'})$) is clockwise from $c(i_\ell, j_{\ell'})$ (resp. $c(i_\ell, j_\ell)$).
In all other instances where the chords corresponding to $X_{i_\ell, j_\ell}$ and $X_{i_{\ell'}, j_{\ell'}}$ intersect at a marked point, one shows that the unique exceptional sequence $\xi = (V_1, V_2)$ with $V_i$ corresponding to a chord $c_i$ for $i = 1, 2$ determined by $X_{i_\ell, j_\ell}$ and $X_{i_{\ell'}, j_{\ell'}}$ has $c_1$ appearing clockwise from $c_2$. This condition on exceptional pairs translates into the good labeling property for diagrams. $\square$

# 4 Mutation of oriented chord diagrams

In this section, we will develop a process of mutation for oriented diagrams that is analogous to the previously defined mutation for quivers and exchange matrices. The following lemma gives a way to associate an oriented diagram to any given **c-matrix**.

**Lemma 1** Let $C \in \mathbf{c-mat}(Q)$ with $\{\vec{c}_i\}_{i \in [n]}$ its $\mathbf{c}$-vectors. Let $\vec{c}_i = \pm \dim(X_{i_1, i_2})$ where the sign of $\vec{c}_i$ is determined by $C$. There is an injective map $\mathbf{c-mat}(Q) \to \vec{D} := \{\text{oriented diagrams } \vec{d} = \{\vec{\iota}(i_\ell, j_\ell)\}_{\ell \in [n]}\}$ given by

$$ \vec{c}_i \mapsto \begin{cases} \vec{\iota}(i_1, i_2) & : \quad \vec{c}_i \text{ is positive} \\ \vec{\iota}(i_2, i_1) & : \quad \vec{c}_i \text{ is negative.} \end{cases} $$

Thus each $\mathbf{c}$-matrix $C$ determines a unique oriented diagram denoted $\vec{d}_C$ with $n$ oriented chords.

The next lemma will be helpful in describing mutation of oriented diagrams in this section. It will also be helpful in classifying $\mathbf{c}$-matrices in the next section.

**Lemma 2** Let $R \in EG(\hat{Q})$, let $B = (b_{ij})$ denote its exchange matrix with $\mathbf{c}$-matrix $C$, and let $\vec{d}_C$ denote the oriented diagram associated to $C$. If $b_{kj} \neq 0$ for some $k, j \in [n]$, then the oriented chords $\vec{c}_k(i_1(k), i_2(k))$ and $\vec{c}_j(i_1(j), i_2(j))$ of $\vec{d}_C$ corresponding to $k$ and $j$ share an endpoint.

We have found that oriented diagrams arising from $\mathbf{c}$-matrices via Lemma 1 have certain chords which share an endpoint via Lemma 2. We now keep track of how oriented diagrams are affected when their corresponding $\mathbf{c}$-matrices are mutated (via the mutation of exchange matrices in Section 2.1). Just as for quivers, mutation of diagrams is a local property–that is, the chords which do not share an endpoint with the mutating chord are not affected by mutation. The way that intersecting chords are affected depends on exactly which endpoint they share. In the theorem below, we give one of our main results–a mutation formula for oriented diagrams arising from $\mathbf{c}$-matrices.

**Theorem 4** Let $R \in EG(\hat{Q})$, let $B = (b_{ij})$ denote its exchange matrix with $\mathbf{c}$-matrix $C$, and let $\vec{d}_C$ denote the oriented diagram associated to $C$. Then for any $k \in [n]$, $\vec{d}_{\mu_k C}$ is obtained from $\vec{d}_C$ by the following process

i) if $j \in [n]$, $b_{kj} \neq 0$, and $\mathrm{sgn}(b_{kj}) \neq \mathrm{sgn}(\vec{c}_k(R))$, replace $\vec{c}_j(i_1(j), i_2(j))$ with $\vec{c}_j((i_1(j))', (i_2(j))')$ where

a) $(i_1(j))' = i_2(k)$, $(i_2(j))' = i_2(j)$ if $i_1(k) = i_1(j)$,

b) $(i_1(j))' = i_1(j)$, $(i_2(j))' = i_1(k)$ if $i_2(k) = i_2(j)$,

c) $(i_1(j))' = i_1(k)$, $(i_2(j))' = i_2(j)$ if $i_2(k) = i_1(j)$,

d) $(i_1(j))' = i_1(j)$, $(i_2(j))' = i_2(k)$ if $i_1(k) = i_2(j)$.

ii) replace $\vec{c}_k(i_1(k), i_2(k))$ with $\vec{c}_k(i_2(k), i_1(k))$.

**Remark 1** Our notion of mutation expands on Araya's notion of mutation of exceptional pairs, which is an operation on unoriented chord diagrams (see [Ara13, Lemma 5.2]).
**Remark 2** The process of oriented diagram mutation requires the information of the mutable part of the ice quiver $R$.

We conclude this section with an example of mutation of oriented chord diagrams associated to $c$-matrices in type $A_3$. Letting $R = \hat{Q}$ with exchange matrix $B$, we first apply $\mu_1$. We use both $i)$ and $ii)$ in Theorem 4 to obtain $\vec{d}_{\mu_1 C}$. Note that the chord $\vec{c}(2, 3)$ corresponding to 3 was not affected. Next, we apply $\mu_3$ to $B' = \mu_1 B$. Since $\operatorname{sgn}(b'_{32}) = 1 = \operatorname{sgn}(\vec{c}_3(\mu_1 R))$, we only use $ii)$ from Theorem 4 to obtain $\vec{d}_{\mu_3 \mu_1 C}$. Notice that the chord $\vec{c}(0, 1)$ corresponding to 1 was not affected.

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

# 5 Reachable CECs and classification of c-matrices

The bijection in Theorem 2 associates to every CEC $\bar{\xi}$ a corresponding chord diagram $d$. It is worth noting that in $A_3$, there do not exist oriented versions of the following three diagrams obtainable by diagram mutation.

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

This behavior occurs in type $A_n$ for every $n \ge 3$. In this section, we classify exactly which CECs appear by classifying diagrams instead. Along the way, we obtain a diagrammatic classification of $c$-matrices.

A CEC $\bar{\xi}$ is said to be **reachable** if there exists an orientation of the diagram $d$ of $\bar{\xi}$ (see Theorem 2), denoted $\vec{d}$, such that $\vec{d} = \vec{d}_C$ for some $C \in \mathbf{c}$-mat($Q$). Let $\vec{d} \in \vec{D}$ and let $k \in [0, n]$ denote a marked point on the disk. Define the following subsets of the vertices of the disk

$$ \mathrm{out}(\vec{d}, k) := \{i \in [0, n] : \vec{c}(k, i) \in \vec{d}\} \quad \text{and} \quad \mathrm{in}(\vec{d}, k) := \{j \in [0, n] : \vec{c}(j, k) \in \vec{d}\}. $$

**Lemma 3** Let $C \in \mathbf{c}$-mat($Q$), let $k \in [0, n]$ be any marked point of the disk, and let $I := \{i_1 < i_2 < \cdots < i_m\} \subset [0, n]$ denote the vertices of the disk that are connected to $k$ in $\vec{d}_C$. Then $\vec{d}_C$ is **weakly separated** at $k$ in the sense that there exists $s, t \in [m]$ such that $\mathrm{in}(\vec{d}_C, k) = \{i_s < i_{s+1} < \cdots < i_{t-1} < i_t\}$ and $\mathrm{out}(\vec{d}_C, k) = I \setminus \mathrm{in}(\vec{d}_C, k)$ or one of $\mathrm{out}(\vec{d}_C, k)$ or $\mathrm{in}(\vec{d}_C, k)$ is empty.
This lemma gives some slight restrictions on the orientation of chords in oriented diagrams arising from
**c-matrices**. The following theorem greatly reduces the number of possible configurations.

**Theorem 5** A CEC $\bar{\xi}$ is reachable if and only if there exists an orientation of the chords of its associated diagram $d$, denoted $\vec{d}$, so that $\vec{d}$ is weakly separated at each marked point and $\vec{d}$ has no subdiagram of any of the following forms:

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

The corollary below gives a complete classification of c-matrices in terms of oriented chord diagrams.

**Corollary 1** The injective image of the map $c\text{-mat}(Q) \to \vec{D}$ defined in Lemma 1 consists of exactly the oriented diagrams that are weakly separated at each marked point and which contain none of the configurations of Theorem 5 as subdiagrams.

From this description of c-matrices, we see exactly which oriented diagrams are reachable via diagram mutation.

**6 Exceptional sequences and linear extensions**

In this section, we consider the problem of counting the number of complete exceptional sequences arising
from a given CEC. It turns out this problem can be restated as the problem of counting the number of linear
extensions of certain posets.

Let $n+1$ be the number of marked points on the boundary of the disk. Let $c(i, j)$ be a chord inside the
disk. We define a clockwise (resp. counterclockwise) **rotation** of $c(i, j)$ about $i$ to be $c(i, j-1)$ (resp.
$c(i, j+1)$) where $j-1$ (resp. $j+1$) denotes the congruence class of $j-1$ (resp. $j+1$) mod $n+1$.

Let $d \in \mathcal{D}$. Define the **poset** of $d$, denoted $\mathcal{P}_d$, to be the partially ordered set whose underlying set is the set of chords of $d$ with the relations $x \le y$ if $x$ and $y$ intersect at a marked point $i \in [0, n]$ and $y$ is a chord obtained from $x$ by a sequence of clockwise rotations of $x$ about $i$. This construction defines a poset because any oriented cycle in the Hasse diagram of $\mathcal{P}_d$ arises from a cycle in $d$. Since $d$ is a tree, the diagram has no cycles. In Figure 1, we show a diagram $d \in \mathcal{D}$ and its poset $\mathcal{P}_d$.

<figure><img src="image_8.png" /><figcaption>Fig. 1: A diagram and its poset.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 2: Two diagrams with the same poset.</figcaption></figure>
In general, the map $\mathcal{D} \to \mathcal{P}(\mathcal{D}) := \{\mathcal{P}_d : d \in \mathcal{D}\}$ is not injective. For instance, each of the two diagrams in Figure 2 have $\mathcal{P}_d = \mathbf{4}$ where $\mathbf{4}$ denotes the linearly-ordered poset with 4 elements. Our next result characterizes the posets arising from diagrams in $\mathcal{D}$.

**Theorem 6** A poset $\mathcal{P} \in \mathcal{P}(\mathcal{D})$ if and only if

i) each $x \in \mathcal{P}$ has at most two covers and covers at most two elements

ii) the underlying graph of the Hasse diagram of $\mathcal{P}$ has no cycles

iii) the Hasse diagram of $\mathcal{P}$ is connected.

Let $\mathcal{P}$ be a finite poset with $m = \#\mathcal{P}$. Let $f: \mathcal{P} \to \mathbf{m}$ be an injective, order-preserving map (i.e. $x \le y$ implies $f(x) \le f(y)$ for all $x, y \in \mathcal{P}$) where $\mathbf{m}$ is the linearly-ordered poset with $m$ elements. We call $f$ a linear extension of $\mathcal{P}$. We denote the set of linear extensions of $\mathcal{P}$ by $\mathcal{L}(\mathcal{P})$.

**Theorem 7** Let $d \in \mathcal{D}$ and let $\bar{\xi}$ denote the corresponding complete exceptional collection. Let $\mathrm{CES}(\bar{\xi})$ denote the set of CESs that can be formed using only the representations appearing in $\bar{\xi}$. Then the map $\mathrm{CES}(\bar{\xi}) \to \mathcal{L}(\mathcal{P}_d)$ defined by $(X_{i_1,j_1}, \dots, X_{i_n,j_n}) \xrightarrow{\mathrm{Thm}^3} \{(c(i_\ell, j_\ell), \ell)\}_{\ell \in [n]} \mapsto (f(c(i_\ell, j_\ell)) := \ell)$ is a bijection.

# 7 Applications

Here we showcase some interesting results that follow easily from our main theorems.

## 7.1 Labeled trees

In [SW86, p. 67], Stanton and White gave a nonpositive formula for the number of vertex-labeled trees with a fixed number of leaves. By connecting our work with that of Goulden and Yong [GY02], we obtain a positive expression for this number.

**Theorem 8** Let $T_{n+1}(r) := \{\text{trees on } [n+1] \text{ with } r \text{ leaves}\} \text{ and } \mathcal{D} := \{\text{diagrams } d = \{c(i_\ell, j_\ell)\}_{\ell \in [n]}\}$. Then

$$ \#T_{n+1}(r) = \sum_{d \in \mathcal{D} : d \text{ has } r \text{ chords } c(i_j, i_{j+1})} \#\mathcal{L}(\mathcal{P}_d). $$

**Proof:** Observe that

$$ \sum_{\substack{d \in \mathcal{D} : d \text{ has } r \\ \text{chords } c(i_j, i_{j+1})}} \#\mathcal{L}(\mathcal{P}_d) = \sum_{\substack{d \in \mathcal{D} : d \text{ has } r \\ \text{chords } c(i_j, i_{j+1})}} \#\{\text{good labelings of } d\} \\ = \# \left\{ d(n) \in \mathcal{D}(n) : \begin{array}{l} d(n) \text{ has } r \text{ chords } c(i_j, i_{j+1}) \\ \text{for some } i_1, \dots, i_r \in [0, n] \end{array} \right\} $$

where we consider $i_j + 1 \mod n + 1$. By [GY02, Theorem 1.1], we have a bijection between diagrams $d \in \mathcal{D}$ with $r$ chords of the form $c(i_j, i_{j+1})$ for some $i_1, \dots, i_r \in [0, n]$ with good labelings and elements of $T_{n+1}(r)$. $\square$

**Corollary 2** We have $(n+1)^{n-1} = \sum_{d \in \mathcal{D}} \#\mathcal{L}(\mathcal{P}_d)$.
## 7.2 Reddening sequences

In [Kel12], Keller proves that for any quiver $\mathcal{Q}$, any two reddening mutation sequences applied to $\hat{\mathcal{Q}}$ produce isomorphic ice quivers. As mentioned in [Kel13], his proof is highly dependent on representation theory and geometry, but the statement is purely combinatorial—we give a combinatorial proof of this result for the linearly ordered quiver $\mathcal{Q}$.

Let $R \in EG(\hat{\mathcal{Q}})$. A mutable vertex $i \in R_0$ is called **green** if there are no arrows $j \to i$ in $R$ with $j \in [n+1, m]$. Otherwise, $i$ is called **red**. A sequence of mutations $\mu_{i_r} \circ \dots \circ \mu_{i_1}$ is **reddening** if all mutable vertices of the quiver $\mu_{i_r} \circ \dots \circ \mu_{i_1}(\hat{\mathcal{Q}})$ are red. Recall that an isomorphism of quivers that fixes the frozen vertices is called a **frozen isomorphism**. We now state the theorem.

**Theorem 9** If $\mu_{i_r} \circ \dots \circ \mu_{i_1}$ and $\mu_{j_s} \circ \dots \circ \mu_{j_1}$ are two reddening sequences of $\hat{\mathcal{Q}}$, then there is a frozen isomorphism $\mu_{i_r} \circ \dots \circ \mu_{i_1}(\hat{\mathcal{Q}}) \cong \mu_{j_s} \circ \dots \circ \mu_{j_1}(\hat{\mathcal{Q}})$.

**Proof:** Let $\mu_{i_r} \circ \dots \circ \mu_{i_1}$ be any reddening sequence. Denote by $C$ the **c-matrix** of $\mu_{i_r} \circ \dots \circ \mu_{i_1}(\hat{\mathcal{Q}})$. By Corollary 1, $C$ corresponds to an oriented diagram $\bar{d}_C$ with all chords of the form $\bar{c}(j, i)$ for some $i$ and $j$ satisfying $i < j$. As $\bar{d}_C$ avoids the configurations of Theorem 5, we conclude that $\bar{d}_C = \{\bar{c}(i, i-1)\}_{i \in [n]}$ so $C = -I_n$. Since **c-matrices** are in bijection with ice quivers in $EG(\hat{\mathcal{Q}})$ (see [NZ12, Thm 1.2]) and since $\tilde{\mathcal{Q}}$ is an ice quiver in $EG(\hat{\mathcal{Q}})$ whose **c-matrix** is $-I_n$, we obtain the desired result. $\square$

## 7.3 Noncrossing partitions and exceptional sequences

A **partition** of $[n]$ is a collection $\pi = \{B_\alpha\}_{\alpha \in I} \in 2^{[n]}$ of subsets of $[n]$ called **blocks** that are nonempty, pairwise disjoint, and whose union is $[n]$. We denote the lattice of set partitions of $[n]$ by $\Pi_n$. A set partition $\pi = \{B_\alpha\}_{\alpha \in I} \in \Pi_n$ is called **noncrossing** if for any $i < j < k < \ell$ where $i, k \in B_{\alpha_1}$ and $j, \ell \in B_{\alpha_2}$, one has $B_{\alpha_1} = B_{\alpha_2}$. We denote the lattice of noncrossing partitions of $[n]$ by $NC^A(n)$.

Label the vertices of a convex $n$-gon $S$ with elements of $[n]$ so that reading the vertices of $S$ counterclockwise determines an increasing sequence mod $n$. We can thus regard $\pi = \{B_\alpha\}_{\alpha \in I} \in NC^A(n)$ as a collection of convex hulls $B_\alpha$ of vertices of $S$ where $B_\alpha$ has empty intersection with any other block $B_{\alpha'}$.
Let $n = 5$. The following partitions all belong to $\Pi_5$, but only $\pi_1, \pi_2, \pi_3 \in NC^A(5)$.

$$ \pi_1 = \{\{1\}, \{2, 4, 5\}, \{3\}\}, \pi_2 = \{\{1, 4\}, \{2, 3\}, \{5\}\}, \pi_3 = \{\{1, 2, 3\}, \{4, 5\}\}, \pi_4 = \{\{1, 3, 4\}, \{2, 5\}\} $$

Below we represent the partitions $\pi_1, \dots, \pi_4$ as convex hulls of sets of vertices of a convex pentagon. We see from this representation that $\pi_4 \notin NC^A(5)$.

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

**Theorem 10** Let $k \in [n]$. There is a bijection between $\mathcal{E}(k)$ and the following chains in $NC^A(n+1)$

$$ \left\{ \{\{i\}\}_{i \in [n+1]} < \pi_1 < \dots < \pi_k \in (NC^A(n+1))^{k+1} : \begin{array}{l} \pi_j = (\pi_{j-1} \setminus \{B_\alpha, B_\beta\}) \cup \{B_\alpha \cup B_\beta\} \\ \text{for some } B_\alpha \neq B_\beta \text{ in } \pi_{j-1} \end{array} \right\}. $$
Here we give examples of the bijection from the previous theorem with $k = 4$.

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

# 8 Future directions

In this work, we have only worked out the combinatorics of exceptional sequences associated to the linearly oriented $A_n$ Dynkin diagram. However, exceptional sequences are defined for any acyclic quiver. We have made progress in extending our work to the following quiver of type $D_n$ and would like to extend our results to all acyclic orientations of simply-laced Dynkin diagrams.

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

We have characterized the posets $P_d$ that arise from diagrams $d \in \mathcal{D}$ and have shown that the number of linear extensions of $P_d$ equals the number of complete exceptional sequences that can be formed from the CEC $\bar{\xi}$ corresponding to $d$. In forthcoming work (see [GM]), we will present a method for computing the linear extensions of the posets $P_d$ and explain the connections between such linear extensions and the theory of factorizations of the long cycle $(1, 2, \dots, n+1) \in \mathcal{S}_{n+1}$ by a set of transpositions (see [GY02]).

# Acknowledgements

Helpful insight was given during conversations with E. Barnard, J. Geiger, G. Muller, G. Musiker, D. Rupel, D. Speyer, and G. Todorov. M. Kulkarni helped with some of the diagrams, and P. Achar gave assistance with the French abstract. We thank G. Muller and G. Musiker for their helpful comments on drafts of our abstract and S. A. Csar whose PhD thesis defense inspired us to see the connections between exceptional sequences and linear extensions. We also thank the 2014 Mathematics Research Communities program for giving us an opportunity to work on this exciting problem as well as for giving us a stimulating (and beautiful) place to work.

# References

[Ara13] T. Araya. Exceptional sequences over path algebras of type $A_n$ and non-crossing spanning trees. *Algebr. Represent. Theory*, 16(1):239–250, 2013.
[ASS06] I. Assem, D. Simson, and A. Skowroński. Elements of the representation theory of associative algebras. Vol. 1, volume 65 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2006. Techniques of representation theory.

[Bes03] D. Bessis. The dual braid monoid. Ann. Sci. École Norm. Sup. (4), 36(5):647–683, 2003.

[BY14] T. Brüstle and D. Yang. Ordered exchange graphs. arXiv:1302.6045v4, 2014.

[Cha12] A. N. Chavez. On the c-vectors of an acyclic cluster algebra. arXiv:1203.1415, 2012.

[DWZ10] H. Derksen, J. Weyman, and A. Zelevinsky. Quivers with potentials and their representations II: applications to cluster algebras. J. Amer. Math. Soc., 23(3):749–790, 2010.

[GM] A. Garver and J. Matherne. Linear extensions and exceptional sequences. in preparation.

[GM14] A. Garver and J. Matherne. A combinatorial model for exceptional sequences in type A. arXiv:1412.3365, 2014.

[GR87] A. L. Gorodentsev and A. N. Rudakov. Exceptional vector bundles on projective spaces. Duke Math. J., 54(1):115–130, 1987.

[GY02] I. Goulden and A. Yong. Tree-like properties of cycle factorizations. J. Combin. Theory Ser. A, 98(1):106–117, 2002.

[HK13] A. Hubery and H. Krause. A categorification of non-crossing partitions. arXiv:1310.1907, 2013.

[IT09] C. Ingalls and H. Thomas. Noncrossing partitions and representations of quivers. Compos. Math., 145(6):1533–1562, 2009.

[Kel12] B. Keller. Cluster algebras and derived categories. In Derived categories in algebraic geometry, EMS Ser. Congr. Rep., pages 123–183. Eur. Math. Soc., Zürich, 2012.

[Kel13] B. Keller. Quiver mutation and combinatorial DT-invariants. FPSAC 2013 Abstract, 2013.

[NZ12] T. Nakanishi and A. Zelevinsky. On tropical dualities in cluster algebras. In Algebraic groups and quantum groups, volume 565 of Contemp. Math., pages 217–226. Amer. Math. Soc., Providence, RI, 2012.

[ONAS$^{+}$13] M. Obaid, K. Nauman, W. S. M. Al-Shammakh, W. Fakieh, and C. M. Ringel. The number of complete exceptional sequences for a Dynkin algebra. Colloq. Math., 133(2):197–210, 2013.

[ST13] D. Speyer and H. Thomas. Acyclic cluster algebras revisited. In Algebras, quivers and representations, volume 8 of Abel Symp., pages 275–298. Springer, Heidelberg, 2013.

[SW86] D. Stanton and D. White. Constructive combinatorics. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1986.