🔢 mathematics

Minimum transformation representations of diagram monoids

This paper derives explicit formulae for the minimum transformation degrees of major finite diagram monoids, such as the partition, Brauer, Temperley–Lieb, and Motzkin monoids, by constructing faithful representations that often manifest as partial actions on projections.

Original authors: Reinis Cirpons, James East, James D. Mitchell

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Reinis Cirpons, James East, James D. Mitchell

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, chaotic box of LEGO bricks. Each brick represents a specific rule for how things can connect. Some rules say "connect these two," others say "don't connect anything," and some say "swap these two around." In the world of mathematics, these boxes are called monoids, and the specific ones in this paper are called diagram monoids because you can draw them as pictures of dots connected by lines.

The authors of this paper, Reinis Cirpons, James East, and James Mitchell, asked a very specific question: "What is the smallest, simplest box of LEGO bricks we can build to perfectly recreate the rules of these complex diagram monoids?"

In math-speak, they are looking for the minimum transformation degree. Think of it like this: If you wanted to explain a complex board game to a friend, you could use a massive, 100-page rulebook (the original monoid). But maybe you could also explain the exact same game using a tiny, 5-page cheat sheet (a smaller representation). The paper figures out exactly how small that cheat sheet can be for several famous types of diagram games.

Here is a breakdown of their journey and findings using simple analogies:

1. The Problem: The "Too Big" Rulebook

For a long time, mathematicians knew how to represent these diagram monoids, but the representations were often huge. It was like trying to store a library of books in a warehouse when you could actually fit them all in a backpack.

The Old Way: They knew the answer was "at most the size of the whole monoid," which is a massive number.
The Goal: Find the exact smallest number. For the most famous monoid, the Partition Monoid (which deals with all possible ways to group items), they found a formula that is surprisingly elegant and much smaller than anyone expected.

2. The Method: The "Shadow Play"

How did they find the smallest size? They used a clever trick involving projections and shadows.

Imagine a complex 3D sculpture (the monoid). If you shine a light on it, it casts a shadow on the wall.

The Trick: Instead of trying to map every single piece of the sculpture, they realized they only needed to track how the "shadows" (called projections) move when you apply the rules.
The "Partial" Action: Sometimes, a rule doesn't work on a specific shadow; it just makes it disappear. The authors developed a way to handle these "disappearing" acts. They treated the system like a game where some moves are valid and others are "off-limits" for certain pieces.

They discovered that for most of these monoids, the "cheat sheet" size is determined by counting specific, simple patterns (like how many ways you can arrange 1, 2, or 3 items) and then adding a little bit of math magic to it.

3. The Results: Famous Number Sequences

The most exciting part of the paper is that the answers aren't just random big numbers. They are built from famous, beautiful sequences that mathematicians have studied for centuries.

Think of these sequences as "families" of numbers:

Bell Numbers: Count how many ways you can group a set of friends into teams.
Catalan Numbers: Count how many ways you can arrange parentheses or walk up stairs without going below the ground.
Motzkin Numbers: A cousin of Catalan numbers, counting paths that can also stay flat.

The Big Discovery:
The paper proves that the size of the smallest representation for these monoids is directly related to these families.

For the Partition Monoid (the big boss), the size is roughly half the difference between three consecutive Bell numbers.
For the Temperley-Lieb Monoid (used in physics to study magnets), the size is related to Catalan numbers.
For the Brauer Monoid (used in quantum physics), the formula is a bit more complex, involving "double factorials" (multiplying every other number down to 1), but it still follows a strict pattern.

4. Why Does This Matter?

You might ask, "Who cares about the smallest box for LEGO rules?"

Efficiency: In computer science, if you want to simulate these mathematical structures, using the smallest possible representation saves massive amounts of memory and processing power.
Understanding Structure: Finding the minimum size is like finding the "DNA" of the structure. It tells us the fundamental complexity of the system. If the number is small, the system is simpler than it looks. If it's huge, the system is deeply complex.
New Tools: The authors didn't just find the numbers; they invented new ways to "see" these structures (using the shadow/projection method). These new tools can now be used by other mathematicians to solve similar problems in different fields.

Summary Analogy

Imagine you have a massive, intricate clockwork machine with thousands of gears (the diagram monoid).

Before this paper: We knew we could build a model of it, but it might take a warehouse full of gears.
This paper: The authors figured out that you can actually build a perfect, working model of the machine using a specific, much smaller set of gears. They even gave you the exact recipe (the formula) to count how many gears you need, and that recipe turns out to be made of the same "ingredients" (Bell, Catalan, Motzkin numbers) that appear in nature, art, and other parts of math.

They took a problem that seemed to require a supercomputer to solve and turned it into a beautiful, hand-calculable formula.

1. Problem Statement

The paper addresses the problem of determining the minimum transformation degree, denoted $\deg(M)$ , for various families of finite diagram monoids.

Definition: For a finite semigroup (or monoid) $M$ , $\deg(M)$ is the smallest integer $n$ such that $M$ embeds into the full transformation monoid $T_n$ (the set of all self-maps on a set of size $n$ ).
Context: While Cayley's Theorem guarantees that any finite monoid of size $|M|$ embeds in $T_{|M|}$ , finding the minimal $n$ is notoriously difficult. For many algebraic structures, this invariant interacts unintuitively with standard constructions.
Target Objects: The authors focus on diagram monoids, which are submonoids of the partition monoid $P_n$ $P_{n}$ . These include:
- The Partition Monoid ( $P_n$ )
- The Partial Brauer Monoid ( $PB_n$ )
- The Planar Partition Monoid ( $PP_n$ )
- The Motzkin Monoid ( $M_n$ )
- The Temperley–Lieb Monoid ( $TL_n$ )
- The Brauer Monoid ( $B_n$ )
Gap: Prior to this work, exact formulas for $\deg(M)$ were unknown for these specific families, with only trivial upper bounds (like $|M|$ ) or partial results available.

2. Methodology

The authors employ a combination of computational experimentation, structural semigroup theory, and combinatorial analysis.

A. Theoretical Framework

Right Congruence Actions: The paper utilizes the fact that any monoid $M$ acts on the quotient $M/\sigma$ for any right congruence $\sigma$ . The degree of this action is an upper bound for $\deg(M)$ . The action is faithful if $\sigma$ contains no non-trivial two-sided congruences.
Regular $\ast$ -Semigroups and Projections: The diagram monoids are regular $\ast$ $*$ -semigroups (possessing an involution $a \mapsto a^*$ $a \mapsto a^{*}$ ). The authors leverage the set of projections $P(M) = \{p \in M : p^2 = p = p^*\}$ $P (M) = {p \in M : p^{2} = p = p^{*}}$ .
- They construct partial actions of $M$ on subsets of projections.
- Specifically, they define a pre-order $\preceq$ (related to the kernel of partitions) and construct an action on a set $Q \subseteq P(M)$ of "low-rank" projections.
Faithfulness via Minimal Congruences: To prove an action is faithful, the authors identify the minimal two-sided congruences of the monoids (classified in previous literature). They demonstrate that their constructed actions separate the generating pairs of these minimal congruences.
Lower Bound Techniques: Proving the lower bound (that no smaller degree exists) involves showing that any faithful action must contain specific disjoint subsets of states. This requires intricate combinatorial arguments involving the structure of Green's relations ( $L, R, J$ ) and the specific generators of the minimal congruences.

B. Computational Discovery

The authors used the Semigroups package for GAP to compute minimal faithful right congruences for small values of $n$ (up to $n=7$ for $P_n$ ). These computations revealed patterns in the structure of the minimal congruences, leading to the discovery of the general construction involving projections of rank $\le 2$ (or specific ranks for $TL_n$ and $B_n$ ).

3. Key Contributions and Results

The paper provides explicit, closed-form formulas for the minimum transformation degree $\deg(M)$ and the minimum partial transformation degree $\deg'(M)$ (where the monoid embeds into the partial transformation monoid $PT_n$ ).

General Formula Structure:
For most monoids, the degree is determined by the size of a specific set of low-rank projections $Q$ :
$\deg(M) = 1 + |Q| \quad \text{and} \quad \deg'(M) = |Q|$
The set $Q$ typically consists of projections with rank $r \le 2$ .

Specific Results:

Monoid ( $M$ )	Condition	Formula for $\deg'(M)$	Sequence/Numbers Involved
Partition ( $P_n$ )	$n \ge 2$	$\frac{B(n+2) - B(n+1) + B(n)}{2}$	Bell Numbers ( $B(n)$ )
Partial Brauer ( $PB_n$ )	$n \ge 2$	$\frac{I(n+2)}{2}$	Involution Numbers ( $I(n)$ )
Planar Partition ( $PP_n$ )	$n \ge 2$	$C(n+2) - 2C(n+1) + C(n)$	Catalan Numbers ( $C(n)$ )
Motzkin ( $M_n$ )	$n \ge 2$	$M(n+2) - M(n+1)$	Motzkin Numbers ( $M(n)$ )
Temperley–Lieb ( $TL_n$ )	$n=2k-1$ (odd)	$C(k+1) - C(k)$	Catalan Numbers
	$n=2k$ (even)	$C(k+2) - 2C(k+1) + C(k)$	Catalan Numbers
Brauer ( $B_n$ )	$n \ge 3$ (odd)	$\frac{n+1}{2} \cdot n!!$	Double Factorials
	$n \ge 4$ (even)	$\frac{(n+4)(n+2)}{8} \cdot (n-1)!!$	Double Factorials

Note: For the Brauer monoid, the method differs significantly. The degree is not simply $1 + |Q|$ for a single set $Q$ ; rather, it involves a linear combination of projection counts, and for even $n$ , $\deg(B_n) < \deg_{rc}(B_n)$ , meaning the minimal faithful action is not a right congruence action.

4. Significance and Impact

Resolution of Open Problems: The paper completely settles the question of minimum transformation degrees for the most well-studied diagram monoids, providing exact formulas where previously only trivial bounds existed.
Connection to Combinatorics: The results reveal deep connections between algebraic representation theory and classical combinatorial sequences (Bell, Catalan, Motzkin, Involution numbers). The degrees are expressed as linear combinations or differences of these famous numbers.
New Techniques:
- The authors developed a robust framework using partial actions on projections for regular $\ast$ -semigroups.
- They demonstrated that for many diagram monoids, the minimal faithful representation is achieved by an action on a small, structured subset of projections (specifically those of low rank), rather than the entire set of projections or the whole monoid.
- The distinction made for the Brauer monoid (where the minimal action is not a right congruence action) highlights the limitations of standard congruence-based methods and necessitates more complex "push-out" constructions.
Computational Algebra: The work bridges the gap between computational experiments (using GAP) and theoretical proof, showing how small-scale data can guide the discovery of general structural theorems.

In summary, the paper provides a comprehensive solution to a difficult algebraic invariant problem, unifying the study of diagram monoids through the lens of projection actions and combinatorial number theory.