Open Research Index

Fast factorization in diagram monoids

Matthias Fresacher, Willow Stewart, Daniel Tubbenhauer

arXivarxiv/2609.30804Sep 25, 2026math.RAscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2609.30804
curl -X POST /api/v1/records/arxiv/2609.30804/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.30804/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'