Generating naturally labeled posets through matrix extensions, order ideals and automorphism groups

Gi-Sang Cheon; Gukwon Kwon; Hojoon Lee; Samuele Giraudo

arxiv: 2512.17749 · v2 · pith:FAZXGB24new · submitted 2025-12-19 · 🧮 math.CO

Generating naturally labeled posets through matrix extensions, order ideals and automorphism groups

Gi-Sang Cheon , Samuele Giraudo , Gukwon Kwon , Hojoon Lee This is my paper

Pith reviewed 2026-05-21 16:41 UTC · model grok-4.3

classification 🧮 math.CO MSC 06A07

keywords naturally labeled posetsBoolean matricesorder idealsmatrix extensionsfixed-point equationsautomorphism groupssieve algorithmsdistributive lattices

0 comments

The pith

A Boolean matrix extends to a valid poset matrix exactly when the vector v satisfies vA = v and represents an order ideal.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper represents naturally labeled posets on [n] as Boolean matrices and introduces extensions of the form A^v. It proves that the extended matrix remains a valid poset representation if and only if the Boolean vector v is an order ideal of the original poset, which holds precisely when v obeys the fixed-point equation vA = v. This algebraic test supports a sieve algorithm that generates admissible extensions without exhaustive search. The same matrix structure yields a twin-class decomposition that computes automorphism groups, enabling Burnside-style counting of nonisomorphic posets, and the authors outline a generation procedure driven by the topological growth of the poset's distributive lattice.

Core claim

A^v defines a valid poset matrix if and only if the Boolean vector v represents an order ideal of the poset P associated to A, equivalently satisfying the fixed-point equation vA = v. Based on this characterization, a sieve algorithm generates all admissible extension vectors efficiently. The twin-class decomposition of A partitions elements according to identical down- and up-sets and supplies an algebraic foundation for Burnside-type enumeration of nonisomorphic posets on [n] via Aut(A). An algorithmic scheme constructs poset families according to the topological growth of their distributive lattices.

What carries the argument

The matrix extension A^v whose validity is governed by the fixed-point equation vA = v that selects exactly the order ideals.

Load-bearing premise

The initial matrix A must already be a faithful Boolean representation of a naturally labeled poset on [n] whose multiplication rules preserve the axioms of a partial order.

What would settle it

A single Boolean vector v that satisfies vA = v yet produces an A^v that violates transitivity or reflexivity would falsify the claimed equivalence.

Figures

Figures reproduced from arXiv: 2512.17749 by Gi-Sang Cheon, Gukwon Kwon, Hojoon Lee, Samuele Giraudo.

**Figure 1.** Figure 1: Distributive lattice PV4(A) of poset vectors We end this section by noticing that all poset vectors in PVn(A) provide different NL posets on Xn+1 but not all are non-isomorphic. 7 [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

**Figure 2.** Figure 2: The Hasse diagram of P and its poset matrix A. Moreover, P≡ = (X5, ⪯≡) where X5 = {¯0, ¯1, ¯3, ¯4, ¯7}, and its poset matrix are: ¯0 ¯1 ¯3 ¯4 ¯7 A≡ = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

**Figure 3.** Figure 3: The Hasse diagram of P≡ and its poset matrix A≡. Proposition 4.6. Let P ∈ N L(n) have twin classes Xn/≡ = {α1, . . . , αr}. For any α ∈ Xn/≡, define a map π ∶ Aut(P) Ð→ Aut(P≡) by π(φ)(α) = φ(α) ∶= {φ(x) ∶ x ∈ α}. Then π is a group homomorphism and ker(π) = r ∏ i=1 S∣αi∣ . (6) In particular, π is surjective onto Aut(P≡) if and only if π(φ) ∈ Aut(P≡) preserves twin-class sizes, i.e. ∣π(φ)(α)∣ = ∣α∣ for all … view at source ↗

**Figure 4.** Figure 4: Ideal lattice L = J(P) and its sublattice JIrr(L) ≅ N (in red). We now turn to the Birkhoff’s theorem from the matrix point of view. We begin by obtaining a matrix characterization of poset vectors of the poset matrix A, which are exactly same as the characteristic vectors of order ideals of the poset PA. Theorem 5.3. Let A ∈ PM(n) be a poset matrix. Then v ∈ {0, 1} n is a poset vector of A if and only if … view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a matrix encoding for naturally labeled posets and shows how to extend them exactly when a Boolean vector satisfies the fixed-point condition vA = v, which matches order ideals.

read the letter

This paper gives a matrix way to generate naturally labeled posets by extending them only when the added vector is an order ideal, detected by the equation vA = v. The authors represent a poset on the set [n] by its Boolean adjacency matrix A. They then consider extensions of the form A^v and prove that the result remains a valid poset matrix precisely when the Boolean vector v satisfies vA = v. This condition is shown to be equivalent to v corresponding to an order ideal in the original poset. They turn this characterization into a sieve algorithm that efficiently produces all admissible extension vectors. On top of that, they define twin classes by grouping elements that have identical down-sets and up-sets. This partition supports a Burnside-type count of nonisomorphic posets via the automorphism group of A. They close with an algorithmic scheme that builds posets according to the topological growth of their distributive lattices. What stands out is how directly the fixed-point equation captures the order ideal property from the matrix representation. The proof follows from the way the Boolean operations encode the partial order axioms, without needing extra fitting or external data. The sieve then follows as a natural consequence, and the twin-class idea provides a structured way to handle automorphisms that aligns with the matrix setup. If the full derivations hold as indicated, this supplies a constructive algebraic tool for enumeration that could be implemented straightforwardly. The main limitation is that everything rests on starting with a valid initial matrix A for a naturally labeled poset. The method excels at controlled extensions but does not address generating the base cases from scratch. It would strengthen the paper to include explicit computations for small n, such as the number of posets generated up to a certain size, or direct comparisons with existing enumeration methods. The application to Birkhoff's question uses standard Burnside machinery, so the advance is more in the preparatory decomposition than in the final counting formula. This work is aimed at combinatorialists interested in poset generation and enumeration algorithms. A reader looking for new algebraic perspectives on order ideals and symmetries will find concrete value here. The core claims look grounded enough to merit sending it out for peer review.

Referee Report

1 major / 3 minor

Summary. The paper introduces a matrix representation for naturally labeled posets on [n] using Boolean poset matrices A. It proves that the extension A^v yields a valid poset matrix if and only if the Boolean vector v represents an order ideal of the poset associated to A, equivalently satisfying the fixed-point equation vA = v in the Boolean semiring. Building on this, the authors develop a sieve algorithm to generate all admissible extension vectors, introduce a twin-class decomposition of A that partitions elements by identical down- and up-sets, and apply this to Burnside-type enumeration of nonisomorphic posets via the automorphism group Aut(A). The manuscript concludes with an algorithmic generation scheme based on the topological growth of the distributive lattices associated to the posets.

Significance. If the central characterization and its algorithmic consequences hold, the work supplies a new algebraic and constructive approach to generating and enumerating naturally labeled posets. The matrix-extension framework and fixed-point condition provide a systematic incremental construction method, while the twin-class decomposition offers a concrete algebraic handle on automorphism groups for isomorphism-free counting. The topological-growth scheme for distributive lattices adds a lattice-theoretic perspective that may prove useful for families of posets. These elements together address aspects of Birkhoff's enumeration question in a computationally oriented way.

major comments (1)

The central if-and-only-if claim (abstract and main theorem) is stated to follow directly from the definition of A as the order matrix and the preservation of reflexivity, antisymmetry, and transitivity under Boolean extension. A short explicit verification that transitivity of A^v is equivalent to the order-ideal property of v would make the load-bearing step fully transparent; currently the derivation is asserted rather than expanded in a self-contained sequence of equivalences.

minor comments (3)

The term 'topological growth of their distributive lattices' appears in the abstract and final section but is not defined or motivated in the introduction; a brief sentence linking it to the order-ideal lattice would improve accessibility.
Notation for Boolean matrix multiplication and the semiring operations (e.g., whether + denotes OR or XOR) should be fixed once at the beginning and used uniformly; occasional shifts between matrix and vector notation can be clarified.
The sieve algorithm is described at a high level; adding a small-n example (e.g., n=3 or n=4) that lists the generated vectors and confirms they match the known order ideals would strengthen the algorithmic claim without altering the central result.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and constructive recommendation. We agree that an explicit verification of the transitivity equivalence will improve transparency and have revised the manuscript to include it.

read point-by-point responses

Referee: The central if-and-only-if claim (abstract and main theorem) is stated to follow directly from the definition of A as the order matrix and the preservation of reflexivity, antisymmetry, and transitivity under Boolean extension. A short explicit verification that transitivity of A^v is equivalent to the order-ideal property of v would make the load-bearing step fully transparent; currently the derivation is asserted rather than expanded in a self-contained sequence of equivalences.

Authors: We agree that expanding the proof with a self-contained sequence of equivalences for the transitivity condition will make the central characterization fully transparent. In the revised manuscript we have added a short explicit verification immediately after the statement of the main theorem. The added paragraph shows, step by step, that A^v satisfies transitivity if and only if v is an order ideal, by direct appeal to the definitions of Boolean matrix multiplication and the order matrix A. This addition addresses the referee's concern without changing the original argument or length of the paper. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper's central equivalence—that A^v is a valid poset matrix if and only if v is an order ideal of P, equivalently satisfying the fixed-point equation vA = v—is established directly from the definitions of the Boolean poset matrix A for a naturally labeled poset and the matrix extension rule A^v, using Boolean semiring operations that preserve reflexivity, antisymmetry, and transitivity. This is a characterization derived from the order matrix representation rather than a self-referential loop or fitted input. The sieve algorithm, twin-class decomposition, and Burnside enumeration via Aut(A) rely on this foundation plus standard external group theory, without any load-bearing self-citation chains, uniqueness theorems imported from the authors' prior work, or ansatzes smuggled in. The derivation remains self-contained against the initial assumption that A is a valid poset matrix and does not reduce any claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard definitions of posets, Boolean matrices, order ideals, and automorphism groups; no free parameters or invented entities are introduced.

axioms (2)

standard math A naturally labeled poset on [n] can be faithfully represented by a Boolean matrix A satisfying the reflexive, antisymmetric, and transitive properties under Boolean matrix multiplication.
Invoked at the outset when defining the Boolean poset matrix A.
domain assumption The fixed-point equation vA = v exactly captures the down-set closure property of an order ideal.
Central to the if-and-only-if claim in the abstract.

pith-pipeline@v0.9.0 · 5737 in / 1406 out tokens · 37898 ms · 2026-05-21T16:41:58.428362+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

S. P. Avann, The lattice of natural partial orders, Aequationes Mathematicae 8, 95–102 (1972)

work page 1972
[2]

Bevan, G.-S

D. Bevan, G.-S. Cheon, S. Kitaev, On naturally labelled posets and permutations avoiding 12–34, European J. of Combinatorics, 126, May 2025, 104117

work page 2025
[3]

Birkhoff, Lattice Theory, American Mathematical Society Colloquium Publications, vol

G. Birkhoff, Lattice Theory, American Mathematical Society Colloquium Publications, vol. 25, American Mathematical Society, Providence, 1948

work page 1948
[4]

Brinkmann and B

G. Brinkmann and B. McKay, Posets on up to 16 Points, Order 19, 147–179 (2002)

work page 2002
[5]

Cheon, B

G.-S. Cheon, B. Curtis, G. Kwon and A. Mwafise, Riordan posets and associated incidence matrices, Linear Algebra and its Applications, 632, 308–331 (2022)

work page 2022
[6]

B. A. Davey and H. A. Priestley, Introduction to lattices and order, Cambridge University Press, 2002

work page 2002
[7]

Day, Characterizations of finite lattices that are bounded-homomorphic images of sub- lattices of free lattices, Canadian Journal of Mathematics, 31(1), 69–78 (1979)

A. Day, Characterizations of finite lattices that are bounded-homomorphic images of sub- lattices of free lattices, Canadian Journal of Mathematics, 31(1), 69–78 (1979)

work page 1979
[8]

R. A. Dean and Gordon Keller, Natural Partial Orders, Canadian Journal of Mathematics, 20, 535–554 (1968)

work page 1968
[9]

R. P. Dilworth, A Decomposition Theorem for Partially Ordered Sets, Annals of Mathe- matics, 51(1), 161–166 (1950)

work page 1950
[10]

Kim, The number of partially ordered sets, Journal of Combinatorial Theory B, 13(3), 276–289 (1972)

K.-H. Kim, The number of partially ordered sets, Journal of Combinatorial Theory B, 13(3), 276–289 (1972)

work page 1972
[11]

Kim, Boolean matrix theory and applications, Marcel Dekker, Inc

K.-H. Kim, Boolean matrix theory and applications, Marcel Dekker, Inc. 1982

work page 1982
[12]

The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org. 24

work page
[13]

S. U. Mohammad and Md. R. Talukder, Poset matrix and recognition of series-parallel posets, International Journal of Mathematics and Computer Science, 15(1), 107–125 (2020)

work page 2020
[14]

Nijenhuis and H

A. Nijenhuis and H. S. Will, Combinatorial Algorithms: For Computers and Hard Calcu- lators (2nd), Academic Press, Inc. 1978. 25

work page 1978

[1] [1]

S. P. Avann, The lattice of natural partial orders, Aequationes Mathematicae 8, 95–102 (1972)

work page 1972

[2] [2]

Bevan, G.-S

D. Bevan, G.-S. Cheon, S. Kitaev, On naturally labelled posets and permutations avoiding 12–34, European J. of Combinatorics, 126, May 2025, 104117

work page 2025

[3] [3]

Birkhoff, Lattice Theory, American Mathematical Society Colloquium Publications, vol

G. Birkhoff, Lattice Theory, American Mathematical Society Colloquium Publications, vol. 25, American Mathematical Society, Providence, 1948

work page 1948

[4] [4]

Brinkmann and B

G. Brinkmann and B. McKay, Posets on up to 16 Points, Order 19, 147–179 (2002)

work page 2002

[5] [5]

Cheon, B

G.-S. Cheon, B. Curtis, G. Kwon and A. Mwafise, Riordan posets and associated incidence matrices, Linear Algebra and its Applications, 632, 308–331 (2022)

work page 2022

[6] [6]

B. A. Davey and H. A. Priestley, Introduction to lattices and order, Cambridge University Press, 2002

work page 2002

[7] [7]

Day, Characterizations of finite lattices that are bounded-homomorphic images of sub- lattices of free lattices, Canadian Journal of Mathematics, 31(1), 69–78 (1979)

A. Day, Characterizations of finite lattices that are bounded-homomorphic images of sub- lattices of free lattices, Canadian Journal of Mathematics, 31(1), 69–78 (1979)

work page 1979

[8] [8]

R. A. Dean and Gordon Keller, Natural Partial Orders, Canadian Journal of Mathematics, 20, 535–554 (1968)

work page 1968

[9] [9]

R. P. Dilworth, A Decomposition Theorem for Partially Ordered Sets, Annals of Mathe- matics, 51(1), 161–166 (1950)

work page 1950

[10] [10]

Kim, The number of partially ordered sets, Journal of Combinatorial Theory B, 13(3), 276–289 (1972)

K.-H. Kim, The number of partially ordered sets, Journal of Combinatorial Theory B, 13(3), 276–289 (1972)

work page 1972

[11] [11]

Kim, Boolean matrix theory and applications, Marcel Dekker, Inc

K.-H. Kim, Boolean matrix theory and applications, Marcel Dekker, Inc. 1982

work page 1982

[12] [12]

The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org. 24

work page

[13] [13]

S. U. Mohammad and Md. R. Talukder, Poset matrix and recognition of series-parallel posets, International Journal of Mathematics and Computer Science, 15(1), 107–125 (2020)

work page 2020

[14] [14]

Nijenhuis and H

A. Nijenhuis and H. S. Will, Combinatorial Algorithms: For Computers and Hard Calcu- lators (2nd), Academic Press, Inc. 1978. 25

work page 1978