next up previous
Next: Layer cakes as orders Up: Boolean layer cakes Previous: Boolean layer cakes

Introduction

 

Ordered sets obtained from a finite Boolean lattice B by selecting a number of complete level sets of B and imposing the induced order on the subset of B so defined seem to be a common source of problems as different as difficult - even in the case of such an order consisting of just two layers. We call such orders Boolean layer cakes for the obvious graphical reason.

As ordered sets, they have been investigated from quite different points of view. It is the purpose of section 2 to survey the more recent literature for results on ordered sets of this type, to the extent we are aware of them. The major part of the work done is devoted to orders consisting of just two layers of a Boolean lattice, even with further constraints (adjacent layers, middle layers). Main themes are the order dimension, the existence of Hamiltonian cycles, the types of suborders, isotone selfmaps and jump numbers of such orders.

Some layer cakes are even lattices, see Fact 3.2.1. As far as we know, they have never been looked at from this point of view. A striking feature of lattices consisting of the 2-element and the 3-element subsets of some finite set (plus top and bottom) is their large number of large (in a sense to be specified) sublattices. We devote section 3 to the study of some properties of such lattices.

Consequently, this paper is of a somewhat hybrid nature. Surveyed results are cited with full bibliographical references but no hints to proof. ``Fact'' is used to label statements which we feel are known but for which we don't have a direct reference; here, sketches of proofs are included. The traditional ``Proposition-Proof''scheme is reserved to statements which we believe to be new.

Our notation is fairly standard. All ordered sets considered are finite unless ecplicitly stated. We write tex2html_wrap_inline1696 for the Boolean lattice with n atoms and think of it as being explicitly realized as the collection of all subsets of an n-element set X, with set inclusion as order relation. An i-set is any set with i elements. So the elements of tex2html_wrap_inline1696 are arranged in layers, the i-th layer consisting of all i-subsets of X ( tex2html_wrap_inline1746 ). Given any two natural numbers tex2html_wrap_inline1748 , we write [r,s] for tex2html_wrap_inline1752 .

Ordered sets alias orders are written as tex2html_wrap_inline1754 or shortly P if there is no need to emphasize the order relation tex2html_wrap_inline1758 . For tex2html_wrap_inline1760 , tex2html_wrap_inline1762 means that x and y are not comparable, tex2html_wrap_inline1768 that x is a lower neighbor of y. Given r natural numbers tex2html_wrap_inline1776 , we write tex2html_wrap_inline1778 for the Boolean layer cake obtained from tex2html_wrap_inline1696 by selecting layers tex2html_wrap_inline1782 (and the induced order), and call it a r-layer cake. If we think of a specific n-set X used to represent tex2html_wrap_inline1696 , we say that tex2html_wrap_inline1778 is realized on X.


next up previous
Next: Layer cakes as orders Up: Boolean layer cakes Previous: Boolean layer cakes

Jürg Schmid