Wiki

Quiver / exchange matrix

An unlabeled quiver is a skew-symmetric integer matrix up to simultaneous permutation of its rows and columns (relabeling the vertices). The matrix entry b_ij records the signed number of arrows between vertices i and j; the sign gives the direction. The Matrix column on Browse and each quiver page shows this exchange matrix (row-major).

Rank

The number of vertices, i.e. the size n of the n×n exchange matrix. Mutation never changes the rank, so it is shared by every quiver in a mutation class.

Mutation

Mutation at a vertex k is the fundamental operation of cluster theory. It produces a new quiver B′ from B by the skew-symmetric mutation rule:

b′_ij = −b_ij   if i = k or j = k,
b′_ij = b_ij + ( |b_ik|·b_kj + b_ik·|b_kj| ) / 2   otherwise.

Mutation is an involution: mutating twice at the same vertex returns the original quiver.

def mutate(matrix, k):
    n = len(matrix)
    rows = [list(row) for row in matrix]
    for i in range(n):
        for j in range(n):
            if i == k or j == k:
                rows[i][j] = -matrix[i][j]
            else:
                b_ik, b_kj = matrix[i][k], matrix[k][j]
                rows[i][j] = (matrix[i][j]
                    + (abs(b_ik) * b_kj + b_ik * abs(b_kj)) // 2)
    return tuple(tuple(r) for r in rows)

Canonical form & quiver ID

Two matrices that differ only by a relabeling of the vertices are the same unlabeled quiver. To give each isomorphism class a single stable identifier, we compute a canonical form (the unique representative of the class) and hash it. The canonical form is found with nauty (graph canonical labeling) when available, falling back to the lexicographically smallest matrix over all n! relabelings. The ID is Q.n{rank}.{sha256[:16]}; a mutation class is MC.n{rank}.{…}.

def quiver_id(matrix):
    canon = canonical_form(matrix)           # nauty, or lex-min over n! relabelings
    blob = json.dumps(to_lists(canon), separators=(',', ':'))
    return "Q.n%d.%s" % (len(canon), sha256(blob)[:16])

Acyclic

The quiver has no directed cycle (drawing an edge i → j whenever b_ij > 0). Acyclic quivers are the well-understood base case of cluster theory: the path algebra kQ is finite-dimensional and its representation type is defined. Computed by an iterative depth-first three-colouring — a back-edge to a vertex still on the stack (GRAY) witnesses a cycle.

def is_acyclic(matrix):
    n = len(matrix)
    adj = {i: [j for j in range(n) if matrix[i][j] > 0] for i in range(n)}
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    for start in range(n):
        if color[start] != WHITE:
            continue
        stack = [(start, 0)]; color[start] = GRAY
        while stack:
            u, idx = stack[-1]
            if idx < len(adj[u]):
                stack[-1] = (u, idx + 1); v = adj[u][idx]
                if color[v] == GRAY:   return False     # back-edge => cycle
                if color[v] == WHITE:  color[v] = GRAY; stack.append((v, 0))
            else:
                color[u] = BLACK; stack.pop()
    return True

Connected

The underlying undirected graph — an edge wherever b_ij ≠ 0 — is connected. A single-vertex quiver is connected by convention. Computed by a graph traversal from vertex 0: the quiver is connected iff every vertex is reached.

def is_connected(matrix):
    n = len(matrix)
    if n <= 1: return True
    adj = {i: {j for j in range(n) if matrix[i][j] != 0} for i in range(n)}
    seen, stack = {0}, [0]
    while stack:
        v = stack.pop()
        for w in adj[v]:
            if w not in seen: seen.add(w); stack.append(w)
    return len(seen) == n

Max edge weight

The largest |b_ij| in the quiver — the heaviest single arrow-bundle. A quiver is simply-laced exactly when its max edge weight is ≤ 1. The current dataset is generated within the bound |b_ij| ≤ 2.

def max_edge(matrix):
    return max(abs(matrix[i][j])
               for i in range(len(matrix)) for j in range(len(matrix)))

Bipartite

Every vertex is a pure source or a pure sink — no vertex has both an incoming and an outgoing arrow. Equivalently, the vertices two-colour so that every arrow goes from one colour to the other.

def is_bipartite(m):
    n = len(m)
    for i in range(n):
        has_out = any(m[i][j] > 0 for j in range(n))
        has_in  = any(m[i][j] < 0 for j in range(n))
        if has_out and has_in:
            return False
    return True

Abundant

Connected, on at least two vertices, with |b_ij| ≥ 2 for every pair of vertices i ≠ j — every arrow-bundle is a double arrow or heavier. The Markov quiver is the smallest abundant quiver.

def is_abundant(m):
    n = len(m)
    if n < 2: return False
    return all(abs(m[i][j]) >= 2
               for i in range(n) for j in range(i + 1, n))

Planar

The underlying multigraph can be drawn in the plane without crossing edges. Every graph on ≤ 4 vertices is planar (the obstructions K₅ and K₃,₃ need 5+ vertices), so for the current rank ≤ 4 dataset this is always true; it is reported as unknown for larger ranks until a full planarity test is wired in.

Representation type

For an acyclic quiver Q, the path algebra kQ has a representation type — finite, tame, or wild — governing how complicated its indecomposable representations are. It is read off the symmetric Tits form M = 2I − |B|: positive definite ⟹ finite (Dynkin), positive semidefinite ⟹ tame (Euclidean / extended Dynkin), indefinite ⟹ wild. Undefined (null) when Q is not acyclic, since kQ is then infinite-dimensional. The minors are computed with exact integer determinants, so the classification is exact.

def representation_type(m):
    if not is_acyclic(m):
        return None                                   # kQ infinite-dimensional
    n = len(m)
    M = [[2 if i == j else -abs(m[i][j]) for j in range(n)] for i in range(n)]
    if positive_definite(M):       return "finite"    # Dynkin
    if positive_semidefinite(M):   return "tame"      # Euclidean
    return "wild"                                      # indefinite

Symmetry group

The automorphism group of the labeled quiver: all vertex permutations σ that preserve the exchange matrix, b_σ(i)σ(j) = b_ij. Reported as its order, a name (e.g. Z/2, S₃), and a small generating set. Computed by brute force over all n! permutations (exact for small n).

def symmetry_group(m):
    n = len(m)
    elements = [p for p in permutations(range(n))
                if all(m[p[i]][p[j]] == m[i][j]
                       for i in range(n) for j in range(n))]
    return {"order": len(elements), "name": group_name(elements), ...}

Mutation class

The mutation class of a quiver is the set of all quivers reachable from it by any sequence of mutations. It is the natural equivalence class in cluster theory: mutation-class invariants (Dynkin type, mutation-finiteness, the acyclicity conditions) are shared by every member. Each class is generated here by a breadth-first search, with classes that share a quiver glued together (union-find).

Labeled vs. distinct quivers

A mutation class can be viewed two ways. The labeled orbit is every labeled matrix reached by mutation — the same unlabeled quiver appears once per vertex-labeling. The distinct quivers are the underlying isomorphism classes (each quiver ID once). Browse and the class page let you switch between them; exactly one distinct quiver is the canonical representative (the lex-minimal matrix over all relabelings of the whole orbit).

def canonical_class_rep(labeled_matrices):
    # lex-min over all relabelings of all matrices in the orbit
    return min((apply_permutation(m, perm)
                for m in labeled_matrices
                for perm in permutations(range(len(m)))), key=lex_key)

Dynkin type

For a mutation-finite class of finite type, the Cartan–Killing label of the corresponding root system (A_n, D_n, E₆, E₇, E₈, …). These are exactly the classes whose acyclic members have positive-definite Tits form. Null for open / infinite-type classes.

Mutation-finite / mutation type

A class is mutation-finite (closed) if its mutation class is a finite set, and mutation-infinite (open) otherwise. Generation explores within a bounded region (|b_ij| ≤ 2); a class that never escapes the bound is proved finite, while one that hits the boundary is infinite. The class page distinguishes:

• Mutation-finite (proved) — the whole class was enumerated.
• Mutation-infinite (proved) — a bounded mutation reached |b_ij| ≥ 3 (Derksen–Owen).
• Mutation-infinite (expected) — strong evidence but not yet a proof.

Mutation class size

The number of labeled matrices in the mutation class (the size of the labeled orbit). Finite for mutation-finite classes; rendered as ∞ for open classes, where the listed number is the explored portion only.

Explored frontier

For an open class, the number of explored quivers that have a mutation leaving the bounded region — the boundary of what was enumerated. It measures how much of an infinite class the bounded search saw.

Mutation-acyclic

A class is mutation-acyclic if some quiver in it is acyclic. Searching the class for an acyclic member proves True directly, and a fully-explored (closed) class with no acyclic member proves False.

def class_is_mutation_acyclic(members, is_open):
    if any(is_acyclic(m) for m in members):
        return True
    return False if not is_open else None    # closed: proved; open: unknown

For an open class the search alone can only say unknown. We then use heredity: mutation-acyclicity is inherited by induced subquivers, so if any member contains an induced subquiver already known not to be mutation-acyclic, the whole class is not mutation-acyclic. The base case is the Markov quiver (rank 3, all |b_ij| = 2, cyclically oriented), whose entire mutation class is just two cyclic quivers — never acyclic. Resolving classes in ascending rank lets that propagate upward.

# By heredity a not-mutation-acyclic subquiver of any size forces a
# not-mutation-acyclic (n-1)-subquiver, so deleting one vertex suffices.
def has_known_non_ma_subquiver(members, known_false):
    for m in members:
        n = len(m)
        if n < 4:                                  # smallest is Markov (rank 3)
            continue
        for k in range(n):                          # delete one vertex
            if known_false.get(quiver_id(delete_vertex(m, k))):
                return True
    return False

Banff

The Banff condition is a sufficient combinatorial criterion for local acyclicity of the cluster algebra (Muller). It is checked by recursive source-deletion: a quiver passes if it is acyclic, or it has a source vertex k and a neighbour j such that deleting k and (separately) deleting j each leave a quiver whose mutation class still satisfies the condition. The search runs over the mutation class.

def check_condition(q, kind):           # kind in {"banff", "louise", "p_prime"}
    if is_acyclic(q):
        return True                                 # base case
    for k in sources(q):                            # a source vertex
        if not cond_class(delete_vertex(q, k), kind):
            continue
        if kind == "p_prime":
            return True                             # P': one deletable source suffices
        for j in neighbours(k, q):                  # Banff/Louise also need a neighbour j
            if not cond_class(delete_vertex(q, j), kind):
                continue
            if kind == "banff":
                return True
            if cond_class(delete_two(q, k, j), kind):   # Louise also needs Q \ {k, j}
                return True
    return False

Louise

The Louise condition strengthens Banff: in addition to the deletions of the source k and a neighbour j, the quiver with both k and j removed must again satisfy the condition (the third branch in the code above). Louise also implies local acyclicity.

P′

The P′ condition is the weakest of the three source-deletion criteria: a quiver passes if it is acyclic, or it has a source k whose deletion leaves a quiver still satisfying P′ — no neighbour condition is required. (A distinct stronger property P is not yet tracked.)

Three-state results & provenance

The semidecidable properties (Banff, Louise, P′) are reported with three states, never a guess:

• Yes — a witness (mutation sequence + source-deletion certificate) was found.
• No — the search was provably exhaustive (the whole finite mutation class was covered with no depth, timeout, or arrow-weight truncation) and no witness exists.
• Unknown — the search was truncated before a witness or a proof.

A truncated flag is threaded through the entire search; a No is only reported when nothing was ever truncated, so it is a genuine proof rather than a failed bounded search. The class page records this provenance for each property.