Algorithmic Problems in Categories of Partitions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916604412952576 |
|---|---|
| author | Faroß, Nicolas Volz, Sebastian |
| author_facet | Faroß, Nicolas Volz, Sebastian |
| contents | Categories of partitions are combinatorial structures arising from the representation theory of certain compact quantum groups and are linked to classical diagram algebras such as the Temperley-Lieb algebra. In this paper, we present efficient algorithms and data-structures for partitions of sets and their corresponding category operations, including a concrete implementation in the computer algebra system OSCAR. Moreover, we show that there exists a category of partitions for which the natural computational problems of deciding membership of a given partition as well as counting partitions of a given size are algorithmically undecidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05373 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithmic Problems in Categories of Partitions Faroß, Nicolas Volz, Sebastian Data Structures and Algorithms Quantum Algebra Categories of partitions are combinatorial structures arising from the representation theory of certain compact quantum groups and are linked to classical diagram algebras such as the Temperley-Lieb algebra. In this paper, we present efficient algorithms and data-structures for partitions of sets and their corresponding category operations, including a concrete implementation in the computer algebra system OSCAR. Moreover, we show that there exists a category of partitions for which the natural computational problems of deciding membership of a given partition as well as counting partitions of a given size are algorithmically undecidable. |
| title | Algorithmic Problems in Categories of Partitions |
| topic | Data Structures and Algorithms Quantum Algebra |
| url | https://arxiv.org/abs/2502.05373 |