2025/12/19 by Gi‐Sang Cheon, Cheon, Gi-Sang, Samuele Giraudo +3
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Combinatorial Mathematics #Polynomial and algebraic computation
paper · doi:10.48550/arxiv.2512.17749
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 Av. We show that Av defines a valid poset matrix if and only if the Boolean vector v∈\mathbb Bn 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.