Cardinalities of Kiselman monoids and their parity asymptotics
Abstract
The cardinalities of Kiselman's semigroups Kn are known to grow double exponentially in n: the sequence 2−n/2log2|Kn| converges along the even and odd n subsequences to positive limits ceven and codd that appear to coincide. In this paper we prove that they are indeed distinct. Since Kiselman's semigroups are ℒ-trivial, the suffix relation defines a partial order on Kn. We introduce the \emph{Kiselman transform} Kis(P) of a poset P, a construction recovering the poset associated with Kn+1 from that associated with Kn. Counting strictly increasing chains in P and Kis(P) yields a linear recurrence governed by a symmetric infinite matrix with explicit binomial entries. This can be used towards efficiently computing |Kn|, allowing the values listed in OEIS sequence A125625 to be extended beyond n=14. A generating functions analysis gives formulas for the above asymptotic limits, together with rigorous numerical bounds establishing that ceven − codd = 1.9945066605…×10−6
Related
- Ideal Structures in Idealizations and Cardinalities of Annihilating Ideals
- Cardinalities of Jordan Diophantine sets of upper triangular integer matrices
- Exact diameter compression for four-point sumset cardinalities
- Explicit Bounds for Restricted Invertibility with Prescribed Group Cardinalities
- Federated Clustering with Unknown Local and Global Cluster Cardinalities
BibTeX
@misc{dandrea2026cardinalities,
title = {{Cardinalities of Kiselman monoids and their parity asymptotics}},
author = {Alessandro D'Andrea and Salvatore Stella},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14331},
eprint = {2610.14331},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14331},
}
RIS
TY - UNPB
TI - Cardinalities of Kiselman monoids and their parity asymptotics
AU - Alessandro D'Andrea
AU - Salvatore Stella
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.14331
UR - https://arxiv.org/abs/2610.14331
AB - The cardinalities of Kiselman's semigroups K_n are known to grow double exponentially in n: the sequence 2^−n/2log_2|K_n| converges along the even and odd n subsequences to positive limits c_even and c_odd that appear to coincide. In this paper we prove that they are indeed distinct. Since Kiselman's semigroups are ℒ-trivial, the suffix relation defines a partial order on K_n. We introduce the \emph{Kiselman transform} Kis(P) of a poset P, a construction recovering the poset associated with K_n+1 from that associated with K_n. Counting strictly increasing chains in P and Kis(P) yields a linear recurrence governed by a symmetric infinite matrix with explicit binomial entries. This can be used towards efficiently computing |K_n|, allowing the values listed in OEIS sequence A125625 to be extended beyond n=14. A generating functions analysis gives formulas for the above asymptotic limits, together with rigorous numerical bounds establishing that c_even − c_odd = 1.9945066605…×10^−6
ER -