Fast factorization in diagram monoids
We give explicit algorithms that factor elements of the standard diagram monoids into their usual generators, extending sorting from permutations to partial matchings and set partitions.
Data
- Title: Fast factorization in diagram monoids
- Authors: Matthias Fresacher, Willow Stewart and Daniel Tubbenhauer
- Status: Preprint, 2026. Comments welcome.
- Code: GitHub
- arXiv: https://arxiv.org/abs/2609.30804
- MSC 2020: Primary: 20M20, 68W40; Secondary: 05A16, 20M05.
Abstract
We give explicit algorithms that factor elements of the standard diagram monoids into their usual generators. These algorithms generalize sorting from permutations to partial matchings and set partitions. In every case the worst-case complexity is \(n^2\), which is optimal for algorithms that explicitly list the factors. We also determine the average complexity of our algorithms.
What is the point?
Sorting a permutation means writing it as a product of adjacent swaps. Diagram monoids replace permutations by diagrams that may also have cups, caps, isolated vertices or larger blocks. The natural analogue of sorting is therefore to factor a diagram into the standard local generators.
The paper does this explicitly for the standard families: Temperley–Lieb, planar rook, Motzkin, planar partition, symmetric, Brauer, rook, rook–Brauer and partition monoids. In all nine cases the minimal worst-case runtime is quadratic. The average behavior has two regimes: it is \(\Theta(n^{3/2})\) for the four planar families and \(\Theta(n^2)\) for the five nonplanar families.
The first picture
Temperley--Lieb rainbow diagrams from the paper. These force the quadratic lower bound for explicit factorization.
Runtime snapshot
The three ingredients
Crossings, cups, caps, isolated vertices and block operations play the role of adjacent swaps.
Each family gets a concrete factorization procedure whose output can be read directly as a word in the standard generators.
Dyck paths, Motzkin numbers, telephone numbers, Bell numbers and related asymptotics explain the different average exponents.
A few extra words
The algorithms are designed for fast explicit factorization, not for producing geodesic words. Since some diagrams require quadratically many generators, any algorithm that actually prints such a factorization already needs quadratic time in the worst case. The algorithms attain this order, so the worst-case runtime is optimal.
The common quadratic worst case hides a useful distinction: planarity strongly reduces the typical amount of displacement and nesting, whereas the nonplanar families retain enough global disorder for quadratic average behavior.
The accompanying GAP code implements the factorization algorithms and experiments with their lengths.