A pair of four-element horizontal generating sets of a partition lattice
Gábor Czédli University of Szeged
Abstract:
Let
$\lfloor x \rfloor$ and
$\lceil x\rceil $ denote the lower integer part and the upper integer part of a real number
$x$, respectively. Our main goal is to construct four partitions of a finite set
$A$ with
$n\geq 7$ elements such that each of the four partitions has exactly
$\lceil n/2\rceil$ blocks and any other partition of
$A$ can be obtained from the given four by forming joins and meets in a finite number of steps. We do the same with
$\lceil n/2\rceil-1$ instead of
$\lceil n/2\rceil$, too. To situate the paper within lattice theory, recall that the partition lattice
$\mathrm{Eq}(A)$ of a set
$A$ consists of all partitions (equivalently, of all equivalence relations) of
$A$. For a natural number
$n$,
$[n]$ and
$\mathrm{Eq}(n)$ will stand for
$\{1,2,\dots,n\}$ and
$\mathrm{Eq}([n])$, respectively. In 1975, Heinrich Strietz proved that, for any natural number
$n\geq 3$,
$\mathrm{Eq} (n)$ has a four-element generating set; half a dozen papers have been devoted to four-element generating sets of partition lattices since then. We give a simple proof of his just-mentioned result. We call a generating set
$X$ of
$\mathrm{Eq}(n)$ horizontal if each member of
$X$ has the same height, denoted by
$h(X)$, in
$\mathrm{Eq} (n)$; no such generating sets have been known previously. We prove that for each natural number
$n\ge 4$,
$\mathrm{Eq}(n)$ has two four-element horizontal generating sets
$X$ and
$Y$ such that
$h(Y)=h(X) +1$; for
$n\geq 7$,
$h(X)= \lfloor n/2 \rfloor$.
Keywords:
Partition lattice, Equivalence lattice, Minimum-sized generating set, Horizontal generating set, Four-element generating set.
Language: English
DOI:
10.15826/umj.2025.1.004
Fulltext:
PDF file (223 kB)