next up previous
Next: Large sublattices of Boolean Up: Layer cakes as lattices Previous: Layer cakes as lattices

Prelude: Maximal sublattices of (distributive) lattices

 

Let L be any (finite) nontrivial distributive lattice. We write tex2html_wrap_inline3086 for the number of proper maximal sublattices of L and tex2html_wrap_inline3090 for the number of proper maximal (0,1)-sublattices of L. We are interested in the relations between the numbers tex2html_wrap_inline3086 , tex2html_wrap_inline3090 and | L|. In [1], the following results were proved:

(i) tex2html_wrap_inline3100 and (ii) tex2html_wrap_inline3102 iff L is a chain.

The proof is based on Birkhoff duality (in the finite case), replacing finite distributive lattices by their dual finite ordered sets of join-irreducibles, and this is the point where critical pairs as considered in subsection 2.1again crop up - although in a slightly more general form. Here are the salient facts:

Let tex2html_wrap_inline3106 be any ordered set. Call an ordered pair (x,y) of elements of P *critical iff tex2html_wrap_inline3112 and for all tex2html_wrap_inline1820 , u<x implies tex2html_wrap_inline3118 and v>y implies tex2html_wrap_inline3122 . Every critical pair is *critical, but not vice versa: A *critical pair may be comparable, and this happens exactly iff y is the unique lower neighbor of x and x is the unique upper neighbor of y. Hashimoto [31] was the first to observe that there is a bijective correpondence between the proper maximal (0,1)-sublattices of a finite distributive lattice L on one side and the *critical pairs of the dual of L on the other. See [1] for details; the results on tex2html_wrap_inline3086 resp. tex2html_wrap_inline3090 cited above are obtained by a careful count of *critical pairs in these dual orders.

Defining tex2html_wrap_inline3140 , we have tex2html_wrap_inline3142 and tex2html_wrap_inline3144 iff L is a chain. tex2html_wrap_inline3148 may be made arbitrarily small: Indeed, let tex2html_wrap_inline3150 , then the dual ordered set of L is the n-element antichain tex2html_wrap_inline3156 . Now every pair of elements of tex2html_wrap_inline3156 is *critical, whence tex2html_wrap_inline3160 for tex2html_wrap_inline3162 .

A natural question is whether the bound tex2html_wrap_inline3164 is characteristic for finite distributive lattices. One of the main results of [2] shows that this is not the case: Indeed, we have tex2html_wrap_inline3164 for any finite bounded lattice L (where L is bounded iff it can be obtained from the trivial lattice by a sequence of applications of Alan Day's doubling construction for intervals). Every finite distributive lattice is bounded, so this is a much better result whose proof, of course, has nothing to do with counting *critical pairs since no duality theory is available.

Returning to the distributive case, we can give better estmates for tex2html_wrap_inline3148 if we restrict the class of lattices considered. Denote by tex2html_wrap_inline3174 the class of all n-generated distributive lattices ( tex2html_wrap_inline3178 ), let tex2html_wrap_inline3180 be the free distributive lattice on n generators and tex2html_wrap_inline3184 the n-element chain. Then both tex2html_wrap_inline3180 and tex2html_wrap_inline3184 are in tex2html_wrap_inline3192 and we claim that for any tex2html_wrap_inline3194 we have tex2html_wrap_inline3196 . Indeed, if tex2html_wrap_inline3198 generates L, then the sets tex2html_wrap_inline3202 generate distinct proper sublattices tex2html_wrap_inline3204 with tex2html_wrap_inline3206 which are contained in distinct proper maximal sublattices tex2html_wrap_inline3208 . It follows that tex2html_wrap_inline3210 . Turning to tex2html_wrap_inline3180 , note that its dual is tex2html_wrap_inline3214 . Since no element of tex2html_wrap_inline3214 has a unique upper or lower neighbor, *critical and critical pairs coincide for tex2html_wrap_inline3214 and by the count given in 2.1.1 there are exactly n of them. So tex2html_wrap_inline3222 . Clearly, tex2html_wrap_inline3224 , and thus tex2html_wrap_inline3226 . Of course, the exact value of tex2html_wrap_inline3228 remains a mystery, but a reasonable estimate may be obtained from Korshunov's asymptotic estimate for tex2html_wrap_inline3230 given in [36].

What is the range of tex2html_wrap_inline3148 outside bounded (and thus distributive) lattices? Again, Boolean layer cakes provide a hint: Let tex2html_wrap_inline3234 denote, for the moment, the layer cake P(0,1,2;n) realized on tex2html_wrap_inline3068 which is obviously a lattice generated by its atoms. It is not hard to check that the maximal sublattices of tex2html_wrap_inline3234 missing, say, the atom tex2html_wrap_inline3242 are given by tex2html_wrap_inline3244 for some tex2html_wrap_inline3246 . It follows that there are n-1 of them and thus tex2html_wrap_inline3250 , giving tex2html_wrap_inline3252 . We see that tex2html_wrap_inline3254 although tex2html_wrap_inline3256 is neither a chain nor distributive, and that tex2html_wrap_inline3258 for tex2html_wrap_inline3162 .

Of course, tex2html_wrap_inline3234 is not even modular. In [2], subspace lattices L of projective planes are examined and it is shown that their count of maximal sublattices is roughly tex2html_wrap_inline3266 , thus tex2html_wrap_inline3268 . In fact, no modular lattices exceeding this bound have been found so far. This fact and the examples in the preceding paragraph motivated the investigation of Boolean layer cakes to test the asymptotic behaviour of tex2html_wrap_inline3148 .


next up previous
Next: Large sublattices of Boolean Up: Layer cakes as lattices Previous: Layer cakes as lattices

Jürg Schmid