A PAIR OF FOUR-ELEMENT HORIZONTAL GENERATING SETS OF A PARTITION LATTICE

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.