Multisymmetric polynomials on set-theoretic quiver representations

This paper extends the enumeration of eventually constant set-valued quiver representations to finite quivers without sinks by encoding them as directed acyclic graphs and applying a recursive source-removal method to derive cardinality formulas that recover multisymmetric generating polynomials without relying on the matrix-tree theorem.

The Gist

The Big Picture: Mapping a City of One-Way Streets

Imagine you have a city made of different neighborhoods (these are the vertices). Between these neighborhoods, there are one-way streets (these are the arrows). This entire map is called a quiver.

Now, imagine that in each neighborhood, there is a group of people. A representation is a set of rules that tells every person in a neighborhood exactly where to walk next based on the streets available.

• If you are in Neighborhood A, the rule says, "Walk to Neighborhood B."
• If you are in Neighborhood B, the rule says, "Walk to Neighborhood C."

The paper asks a specific question: What happens if we keep following these rules over and over again?

In a normal city, you might get stuck in a traffic loop (a cycle) forever. But this paper is interested in a special kind of city where, no matter where you start, if you walk long enough, you eventually stop wandering and end up at a specific, single meeting spot. The paper calls these "eventually constant" systems.

The Problem: Counting the Possibilities

The authors want to count how many different ways you can set up these walking rules so that everyone eventually ends up at a meeting spot.

In the past, mathematicians could only solve this for very specific, simple city layouts (like a perfect circle of neighborhoods). This paper is a breakthrough because it solves the counting problem for any city layout that doesn't have "dead ends" (sinks) and where you can always keep walking forward.

The Method: Turning Rules into Graphs

To count these possibilities, the authors use a clever trick:

1. The Graph: They turn the abstract rules into a giant picture (a graph) where every person is a dot, and every walking rule is an arrow.
2. The "Forest" Analogy: In a simple city, these rules look like a forest of trees where everyone eventually walks down to a root. But in complex cities, the paths can be messy.
3. Source Removal: The authors developed a new way to count these messy paths. Imagine you are cleaning up a messy room. Instead of trying to count every possible mess at once, you look for the "sources" (the items that aren't being pushed by anything else) and remove them. You repeat this process.
   • They proved that if you remove these "source" items in a specific order, you can calculate the total number of valid configurations using a recursive formula (a recipe that calls itself).

The Math: The "Magic Matrix"

The core of their discovery is a Matrix (a grid of numbers).

• Think of this matrix as a giant instruction manual.
• The paper shows that if you follow the instructions in this matrix (specifically, by calculating its inverse), you get the exact number of ways to set up the walking rules so that everyone eventually stops at a meeting spot.
• They call this the "Cardinality Enumerator." It takes the size of your neighborhoods and the layout of your streets and spits out the answer.

The Special Cases: Jordan and Cyclic Quivers

The paper tests their new "Magic Matrix" on two famous types of city layouts:

1. The Jordan Quiver (The Loop): Imagine one neighborhood with a bunch of loops (like a roundabout with multiple lanes). This is like having one person with multiple different habits. The authors show their formula works here and connects to known results about "eventually constant functions" (like how a computer program eventually stops or repeats).
2. The Cyclic Quiver (The Circle): Imagine neighborhoods arranged in a perfect circle. This is the layout they studied in previous work.
   • The Surprise: In their previous work, they used a famous theorem called the "Matrix-Tree Theorem" (which counts trees in a graph) to get the answer.
   • The New Achievement: In this paper, they use their new "Source Removal" method to get the exact same answer for the cyclic quiver without using the Matrix-Tree Theorem. This proves their new method is powerful enough to replace older, more complicated tools.

The "Multisymmetric" Part

The title mentions "Multisymmetric Polynomials." In simple terms, this means the answer doesn't care which specific person is walking where, only how many people are in each group.

• If you swap Person A and Person B in Neighborhood 1, the total count of valid rules doesn't change.
• The authors' formula respects this symmetry, grouping all the possibilities together efficiently.

Summary

In short, this paper is a new counting tool for mathematicians.

• Old way: You could only count these "eventually stopping" systems in simple, circular cities using a specific, complex theorem.
• New way: The authors created a universal "recipe" (a recursive matrix method) that works for any city layout without dead ends.
• Result: They can now calculate the number of ways to set up these rules for complex networks, and they proved their new method works just as well as the old one for the classic circular cases, but with a more flexible approach.

They didn't just find a number; they found a new way of thinking about how things move through networks and how to count the paths that eventually lead to a stop.

Technical Summary

Technical Summary: Multisymmetric Polynomials on Set-Theoretic Quiver Representations

Problem Statement
This paper addresses the combinatorial enumeration of "eventually constant" set-valued representations of finite quivers. A set-valued representation of a quiver $Q$ assigns a finite set to each vertex and a function to each arrow. A representation is defined as eventually constant if, for all sufficiently long paths in the quiver, the composition of the corresponding functions maps the entire domain into a specific "transversal" (a subset containing exactly one element from each vertex set).

This concept serves as a set-theoretic analogue to nilpotent linear representations of quivers. While previous work by the authors (Green–Holmes–Im) successfully enumerated these representations for equioriented cyclic quivers using the directed matrix-tree theorem, this paper seeks to generalize the enumeration to arbitrary finite quivers without sinks, where every vertex is the target of arbitrarily long paths. The challenge lies in the fact that, unlike the cyclic case, the underlying graph structures induced by these representations are not necessarily forests, rendering standard tree-enumeration techniques inapplicable.

Methodology
The authors develop a framework that encodes set-valued representations as directed acyclic graphs (DAGs) and utilizes a recursive source-removal method to derive generating functions.

1. Graph Encoding: The authors construct an ambient directed multigraph $G(Q)$ where vertices correspond to the elements of the disjoint union of the sets assigned to the quiver's vertices. Edges are labeled by the quiver's arrows. A set-valued representation is identified with a spanning subgraph of $G(Q)$ where each vertex has exactly one outgoing edge per arrow type.
2. Source-Factorizable DAG Assignments: To handle the complexity of general quivers, the authors introduce the concept of a source-factorizable DAG assignment. This is a collection of DAGs satisfying specific axioms regarding how "source" vertices (those with in-degree zero in the subgraph) and their outgoing edges can be attached to or removed from the graphs.
3. Recursive Matrix Enumerators: For source-factorizable assignments, the authors derive a recursive formula for the weighted count of DAGs. They define an attaching weight matrix $M$, indexed by the power set of the vertex set. The entries of $M$ encode the weights of graphs formed by attaching source edges to existing DAGs. The total weight of the desired DAGs is expressed via the inverse of the matrix $(I - M)$, expanded as a finite geometric series due to the strict upper triangularity of $M$.
4. Compression to Cardinality Vectors: To obtain a computable cardinality formula, the authors compress the matrix $M$ (indexed by subsets) into an attaching cardinality matrix $N$. This matrix is indexed by cardinality vectors (vectors in $\mathbb{N}^{Q_0}$ representing the size of the set at each vertex). The uniformity of the weights with respect to set cardinalities allows this reduction, transforming the problem into a matrix operation on the interval of cardinality vectors $[0, V]$.

Key Contributions and Results

• General Enumeration Theorem: The paper establishes a general formula for the cardinality of eventually constant representations for any quiver $Q$ without sinks. The cardinality is given by:
  $$|EC| = V!(I - N)^{-1}_{1, V}$$
  where $V$ is the vector of set sizes, $1$ is the vector of ones, and $N$ is the strictly upper triangular attaching cardinality matrix defined by the quiver's adjacency matrix $A(Q)$.
• Generating Functions: The authors derive generating functions for these representations in both edge variables and vertex variables. In the vertex variable specialization, the generating function is shown to be invariant under permutations of vertices within each set, yielding multisymmetric polynomials.
• Specialization to Jordan and Cyclic Quivers:
  • Jordan Quivers: For a quiver with one vertex and $j$ loops, the authors recover the known recurrence for the number of eventually constant $j$-tuples of endomorphisms. This result aligns with the linear recurrence for labeled quasi-acyclic automata derived by Liskovets.
  • Cyclic Quivers: For equioriented cyclic quivers, the authors derive a closed-form generating function. Notably, this derivation recovers the multisymmetric generating polynomial for the cyclic case without relying on the directed matrix-tree theorem, offering a new combinatorial perspective.
• Alternative Algorithm: For the Jordan quiver, the paper outlines an alternative recursive algorithm based on partitioning the vertex set. This method tracks the successive partitions induced by the equivalence relations of the maps, providing a different computational approach to the generating function.

Significance
The paper claims significance in extending the enumeration of set-theoretic quiver representations beyond the restrictive cyclic case to general quivers. By replacing the matrix-tree theorem with a recursive source-removal method and matrix inversion in the incidence algebra of the subset lattice, the authors provide a unified framework for these combinatorial structures. The work bridges the gap between linear representation theory (nilpotency) and set-theoretic combinatorics (eventual constancy), providing explicit formulas for cardinalities and generating functions that generalize previous results on cyclic quivers and endomorphisms. The derivation of the cyclic case without the matrix-tree theorem is highlighted as a conceptual improvement, avoiding complex algebraic manipulations of $q$-binomial coefficients.