Linear extensions and directed clique counts via modular partitions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912836826955776 |
|---|---|
| author | Santander, Daniela Egas Santoro, Matteo Smith, Jason P. |
| author_facet | Santander, Daniela Egas Santoro, Matteo Smith, Jason P. |
| contents | Counting linear extensions is a fundamental problem in poset theory. It is known to be #P-complete, with polynomial-time formulas available in special cases. In this work, we develop new recursive formulas for counting linear extensions of posets whose modular partitions have particular structure. Specifically, we focus on posets whose incomparability graph has a modular partition with a skeleton that is a tree, a necklace of cliques, or a combination of both. The proofs are constructive and allow for the explicit generation of all linear extensions. We also discuss equivalent formulations of the problem in terms of permutations and directed graphs. The directed graph perspective is related to counting directed simplices in the directed flag complex of a digraph, with applications to understanding higher-order structure in neural circuits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_14482 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Linear extensions and directed clique counts via modular partitions Santander, Daniela Egas Santoro, Matteo Smith, Jason P. Combinatorics Algebraic Topology 06A07, 06B35, 05C20, 05A05, 05E45, 55U10 Counting linear extensions is a fundamental problem in poset theory. It is known to be #P-complete, with polynomial-time formulas available in special cases. In this work, we develop new recursive formulas for counting linear extensions of posets whose modular partitions have particular structure. Specifically, we focus on posets whose incomparability graph has a modular partition with a skeleton that is a tree, a necklace of cliques, or a combination of both. The proofs are constructive and allow for the explicit generation of all linear extensions. We also discuss equivalent formulations of the problem in terms of permutations and directed graphs. The directed graph perspective is related to counting directed simplices in the directed flag complex of a digraph, with applications to understanding higher-order structure in neural circuits. |
| title | Linear extensions and directed clique counts via modular partitions |
| topic | Combinatorics Algebraic Topology 06A07, 06B35, 05C20, 05A05, 05E45, 55U10 |
| url | https://arxiv.org/abs/2601.14482 |