Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 6 min ago
PreprintarXiv licencearXiv

Fast factorization in diagram monoids

  • Matthias Fresacher
  • Willow Stewart
  • Daniel Tubbenhauer
Open at sourcePDFDOICite

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 n2, which is optimal for algorithms that explicitly list the factors. We also determine the average complexity of our algorithms.

Related

  1. A Categorical Realization of the (2-)Category of Monoids via Sch{ü}tzenberger Categories and Strict Factorization Systems
    Xavier Mary
    CompositionalityPeer-reviewedLicence not statedGeneral mathematicsHAL
  2. Presentation of monoids generated by a projection and an involution
    Pascal Caron, Jean-Gabriel Luque, Bruno Patrou
    Semigroup ForumPeer-reviewedCC BY 4.0Full textGeneral mathematicsHAL
  3. Generation of Iterated Wreath Products Constructed from Full Transformation Monoids and Symmetric Groups
    Jiaping Lu
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  4. Enumeration of Upper Triangular Symplectic Renner Monoids
    Reginald Koo, Zhenheng Li
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. Quantized integral models of reductive monoids
    Jingren Chi, Simon Jacques
    arXivPreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{fresacher2026fast,
  title = {{Fast factorization in diagram monoids}},
  author = {Matthias Fresacher and Willow Stewart and Daniel Tubbenhauer},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.30804},
  eprint = {2609.30804},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.30804},
}
RIS
TY  - UNPB
TI  - Fast factorization in diagram monoids
AU  - Matthias Fresacher
AU  - Willow Stewart
AU  - Daniel Tubbenhauer
PY  - 2026
DA  - 2026/09/25
PB  - arXiv
DO  - 10.48550/arxiv.2609.30804
UR  - https://arxiv.org/abs/2609.30804
AB  - 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.
ER  -