Generating naturally labeled posets through matrix extensions, order ideals and automorphism groups
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914573381009408 |
|---|---|
| author | Cheon, Gi-Sang Giraudo, Samuele Kwon, Gukwon Lee, Hojoon |
| author_facet | Cheon, Gi-Sang Giraudo, Samuele Kwon, Gukwon Lee, Hojoon |
| contents | We propose a matrix approach for generating naturally labeled posets by representing each poset $P$ on the set $[n]$ as a Boolean poset matrix $A$. This algebraic representation enables a systematic handling of partial orderings through matrix extensions $A^v$. We show that $A^v$ defines a valid poset matrix if and only if the Boolean vector $v\in\mathbb B^n$ represents an order ideal of the poset $P$ associated to $A$, equivalently satisfying the fixed-point equation $vA=v$. Based on this characterization, we develop a sieve algorithm that generates all admissible extension vectors efficiently. Furthermore, we explore the twin-class decomposition of $A$, which partitions the elements of $P$ according to identical down- and up-sets. This structure provides an algebraic foundation for Burnside-type enumeration for Birkhoff's question on counting nonisomorphic posets on $[n]$ through the automorphism group ${\rm Aut}(A)$. Finally, we present an algorithmic generation scheme for the posets based on the topological growth of their distributive lattices, offering a new approach to constructive enumeration of poset families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_17749 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generating naturally labeled posets through matrix extensions, order ideals and automorphism groups Cheon, Gi-Sang Giraudo, Samuele Kwon, Gukwon Lee, Hojoon Combinatorics 06A07, 05A15, 15B34 We propose a matrix approach for generating naturally labeled posets by representing each poset $P$ on the set $[n]$ as a Boolean poset matrix $A$. This algebraic representation enables a systematic handling of partial orderings through matrix extensions $A^v$. We show that $A^v$ defines a valid poset matrix if and only if the Boolean vector $v\in\mathbb B^n$ represents an order ideal of the poset $P$ associated to $A$, equivalently satisfying the fixed-point equation $vA=v$. Based on this characterization, we develop a sieve algorithm that generates all admissible extension vectors efficiently. Furthermore, we explore the twin-class decomposition of $A$, which partitions the elements of $P$ according to identical down- and up-sets. This structure provides an algebraic foundation for Burnside-type enumeration for Birkhoff's question on counting nonisomorphic posets on $[n]$ through the automorphism group ${\rm Aut}(A)$. Finally, we present an algorithmic generation scheme for the posets based on the topological growth of their distributive lattices, offering a new approach to constructive enumeration of poset families. |
| title | Generating naturally labeled posets through matrix extensions, order ideals and automorphism groups |
| topic | Combinatorics 06A07, 05A15, 15B34 |
| url | https://arxiv.org/abs/2512.17749 |