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

Abstract

Let ⌊x⌋ and ⌈x⌉ 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 ≥ 7 elements such that each of the four partitions has exactly ⌈n∕2⌉ 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 ⌈n∕2⌉- 1 instead of ⌈n∕2⌉, too. To situate the paper within lattice theory, recall that the partition lattice Eq(A) of a set A consists of all partitions (equivalently, of all equivalence relations) of A. For a natural number n, [n] and Eq(n) will stand for {1, 2,…,n} and Eq([n]), respectively. In 1975, Heinrich Strietz proved that, for any natural number n ≥ 3, 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 Eq(n) horizontal if each member of X has the same height, denoted by h(X), in Eq(n); no such generating sets have been known previously. We prove that for each natural number n ≥ 4, Eq(n) has two four-element horizontal generating sets X and Y such that h(Y ) = h(X) + 1; for n ≥ 7, h(X) = ⌊n∕2⌋.