Heights of one- and two-sided congruence lattices of semigroups

Abstract

The height of a poset $P$ is the supremum of the cardinalities of chains in $P$. The exact formula for the height of the subgroup lattice of the symmetric group ${\mathcal{S}}_n$ is known, as is an accurate asymptotic formula for the height of the subsemigroup lattice of the full transformation monoid ${\mathcal{T}}_n$. Motivated by the related question of determining the heights of the lattices of left- and right congruences of ${\mathcal{T}}_n$, we develop a general method for computing the heights of lattices of both one- and two-sided congruences for semigroups. We apply this theory to obtain exact height formulae for several monoids of transformations, matrices and partitions, including: the full transformation monoid ${\mathcal{T}}_n$, the partial transformation monoid ${\mathcal{P}\mathcal{T}}_n$, the symmetric inverse monoid ${\mathcal{I}}_n$, the monoid of order-preserving transformations ${\mathcal{O}}_n$, the full matrix monoid $\mathcal{M}(n,q)$, the partition monoid ${\mathcal{P}}_n$, the Brauer monoid ${\mathcal{B}}_n$ and the Temperley-Lieb monoid ${\mathcal{T}\mathcal{L}}_n$.