Height-bounded mutation to acyclic quivers on four vertices

Introduction

Fomin and Zelevinsky introduced cluster algebras in 2001 as an algebraic setting for total positivity and canonical bases [13]. Their exchange relations are accompanied by mutations of an integer exchange matrix. In the skew-symmetric case, the matrix records a finite quiver without loops or directed two-cycles. Mutation changes its arrows along directed paths of length two.

A quiver is mutation-acyclic if a finite sequence of mutations takes it to a quiver without directed cycles. This property connects the combinatorics to hereditary representation theory. Buan, Marsh, Reineke, Reiten and Todorov developed cluster categories of hereditary algebras [14]; Buan, Marsh and Reiten realized matrix mutation through mutation of cluster-tilting objects [15]. Assem, Brüstle and Schiffler described cluster-tilted algebras as relation extensions of tilted algebras [3].

For three vertices, recognition is governed by descent and a cubic invariant. Assem, Blais, Brüstle and Samson gave a combinatorial decision algorithm by mutating opposite a largest multiplicity [16 §2.5]. Beineke, Brüstle and Hille proved that a directed triangle with multiplicities $x$, $y$, $z$ is mutation-cyclic exactly when $x,y,z \ge2$ and $x^2+y^2+z^2-xyz \le4$ [17 Theorem 1.2]. Their analysis identifies a fundamental region for the mutation action and relates its integral orbits to the Markov equation. In particular, a mutation-acyclic triangle can be made acyclic without increasing its largest multiplicity.

Every full subquiver of a mutation-acyclic quiver is mutation-acyclic [15 Corollary 5.3]. Felikson and Tumarkin proved that every quiver in the mutation class of an acyclic quiver with at least two arrows between every pair of vertices reaches an acyclic representative by decreasing mutations [18 Corollary 3.5 and Remark 3.6]. Each such mutation lowers an arrow multiplicity and raises none. This gives the initial-height bound in that class, in every rank. Four-vertex quivers with missing edges or unit arrows require other local moves.

Fomin and Neville introduced cyclically ordered quivers and mutation invariants obtained from their unipotent companions [19]. A proper mutation changes both the quiver and its cyclic ordering; a totally proper ordering permits these operations through every mutation sequence. Neville proved that every mutation-acyclic quiver has such an ordering [20 Theorem 1.1]. The associated Markov invariant extends the rank-three cubic. For a fixed vertex set and a fixed value of this invariant there are only finitely many acyclic quivers [20 Corollary 6.7]. These results provide finite sets of possible acyclic endpoints, while a bound on the intermediate quivers is still needed for a finite search.

Armstrong-Williams, Hirst, Jackson and Lee studied four-vertex recognition computationally in their 2024 preprint, revised in 2025 [21]. Their 2026 paper [1] corrects the earlier bounded criterion and proves a general path-height bound. If $h$ is the largest initial arrow multiplicity and $m(Q)$ is the Markov invariant in the totally proper class, a mutation-acyclic four-vertex quiver $Q$ reaches an acyclic representative within height $\max\{h,m(Q)\}$. Their resulting decision procedure explores $O(h^{24})$ states. They also show that mutation-acyclicity in ranks at least four has no semialgebraic criterion in the arrow multiplicities.

Conjecture 5.5 of [1] asserts that the term $m(Q)$ can be omitted. The authors checked the conjecture through height three. Thalluri subsequently reported a finite computational verification through height seven, using the authors’ decision procedure for mutation-cyclicity certificates [22]. Throughout the paper quivers are ordinary, so their exchange matrices are integral and skew-symmetric. The height $\operatorname{ht}(Q)$ is the largest arrow multiplicity, with height zero for the quiver with no arrows.

The theorem gives a decision procedure exploring at most $(2h+1)^6 = O(h^6)$ labelled states. Its proof removes height peaks from a path to an acyclic quiver. Two-vertex mutation orbits provide commuting and pentagon replacements. For the remaining configurations, the relation-extension description produces finitely many possible tilted cuts. Explicit indecomposable modules and path-space calculations exclude those cuts. An endpoint argument also excludes a terminal high segment ending at an acyclic quiver.

Mutation and finite-height search

A quiver has a finite labelled vertex set, finitely many arrows, no loops and no oriented cycles of length two. Parallel arrows are allowed. Its exchange matrix $B=(b_{ij})$ is defined by setting $b_{ij}$ equal to the number of arrows $i\to j$ minus the number of arrows $j\to i$. Thus $B$ is skew-symmetric. When the quiver varies, $b_{ij}(Q)$ denotes the signed entry for $Q$. For four vertices we record it by

A positive coordinate denotes arrows from the smaller label to the larger label; a negative coordinate denotes arrows in the opposite direction. The height is $\operatorname{ht}(B)=\max_{i<j}|b_{ij}|$. For an integer $x$, write $[x]_+=\max(x,0)$. Mutation at vertex $k$ gives the matrix $B'=\mu_k(B)$ with

Mutation words are read from left to right: $B_{123}=\mu_3\mu_2\mu_1(B)$. More generally, for a word $w=k_1\cdots k_s$, write $\mu_w=\mu_{k_s}\cdots\mu_{k_1}$ and $Q_w=\mu_w Q$. The empty word acts as the identity. A permutation $\pi$ relabels each old vertex $i$ as $\pi(i)$; its action is

Write $\pi(w)=\pi(k_1)\cdots\pi(k_s)$. Substitution in the mutation formula gives

Cycle notation has its usual direction, so $(123)$ sends 1 to 2, 2 to 3, and 3 to 1. A quiver is acyclic if it has no directed cycle. It is mutation-cyclic if it is not mutation-acyclic. Reversing all arrows or permuting vertex labels preserves height and mutation-acyclicity.

Proof. Enumerate the component of $Q$ in the graph whose vertices are skew-symmetric integral matrices of height at most $h$ and whose edges are mutations remaining within that bound. There are at most $(2h+1)^6$ such matrices. If an acyclic matrix is found, the recorded path proves mutation-acyclicity. Conversely, Theorem 1.1 implies that a mutation-acyclic input has an acyclic matrix in this component. Exhausting the finite component therefore decides the question. □

For $h \ge1$ the number of states is $O(h^6)$. Entries created while testing a mutation have size $O(h^2)$, so each test uses integers with $O(\log(h+1))$ bits. The state bound is polynomial in the numerical height.

Cyclic orderings and the Markov invariant

A cyclic ordering $\omega=\langle v_1,v_2,v_3,v_4\rangle$ is a placement of the vertices on an oriented circle; lists differing by cyclic rotation represent the same ordering. A vertex $k$ is proper if every directed path $i\to k\to j$ meets $i,k,j$ in that clockwise order. A wiggle interchanges adjacent vertices not joined by an arrow. A wiggle class is proper if each vertex is proper in some representative. To mutate properly at $k$, choose such a representative, mutate at $k$, and move $k$ clockwise past its incoming neighbours in the mutated quiver without passing its outgoing neighbours. This gives a well-defined wiggle class. A class is totally proper if it remains proper under every finite sequence of these operations.

For $\omega=\langle v_1,v_2,v_3,v_4\rangle$, set

The signed entries use the indicated vertex order. Define

The value is independent of cyclic rotation, wiggles and proper mutation. Every mutation-acyclic quiver has a unique totally proper class; for an acyclic quiver it comes from a topological order [1 Theorem 2.2]. We write $m(Q)$ for the value in this class, and abbreviate it to $m$ when the quiver is fixed. The polynomial must be evaluated in that ordering, which need not be the fixed label order used for mutation coordinates. For example, in a topological order all six coordinates are nonnegative, so every term in the displayed formula is nonnegative.

The Pfaffian in the fixed label order is

For fixed $Q$, write $p=p(Q)$. Mutation changes its sign, and relabelling changes it by the sign of the permutation. For connected mutation-acyclic quivers on four vertices, the established inequalities [1 Section 2] are

We also use the hereditary property that every full subquiver of a mutation-acyclic quiver is mutation-acyclic, the rank-three criterion that a directed triangle is mutation-cyclic precisely when all its multiplicities are at least two and its Markov constant (the sum of their squares minus their product) is at most four, and the four-vertex vortex obstruction [1 Section 2]. A vortex is a quiver with a directed triangle and a fourth vertex joined to all three triangle vertices as a strict source or strict sink.

Proof. The directed triangle 134 restricts a proper class to the three cyclic orders $\langle1,2,3,4\rangle$, $\langle1,3,2,4\rangle$, $\langle1,3,4,2\rangle$. A restriction to a complete triple persists under wiggles, since none of its pairs can be interchanged. If $a=0$, the first and last orders differ by a wiggle at 12. If $d=0$ or $E=0$, the middle order joins them across 23 or 24. Otherwise the complete triple 234 contains the path $2 \to3 \to4$ when $d>0$, or $3 \to4 \to2$ when $d,E<0$; this excludes the middle order. If $a>0$, we have $d\geq0$. When $d>0$, the complete triple 123 contains $1 \to2 \to3$, leaving only the first order. When $d=0$, $E\ne0$, the complete triple 124 contains $4 \to1 \to2$, leaving the first two orders, which are wiggle equivalent at 23. When $d=E=0$, all three are connected by wiggles at 23, 24. Thus at most one proper class exists. The existence of a totally proper class for a mutation-acyclic quiver identifies it with this class. Substitution in the Markov polynomial gives the formula. □

Acyclic endpoints in two-vertex orbits