next up previous
Next: Layer cakes as lattices Up: Layer cakes as orders Previous: Isotone self-maps and automorphisms

Jump numbers

 

General Boolean layer cakes, that is, cakes obtained by picking an arbitrary collection of level sets from a Boolean algebra, seem to occur in the literature at just one point: In [24], Füredi and Reuter calculate their jump number and determine an optimal linear extension. The author is indebted to Klaus Reuter for bringing [24] to his attention.

Given an ordered set tex2html_wrap_inline3016 and a linear extension L of tex2html_wrap_inline3020 , a jump (of L) is a pair (x,y) of elements of P such that tex2html_wrap_inline1762 in tex2html_wrap_inline3020 but x is covered by y in L. Let s(P;L) be the number of jumps of L; then the jump number of P, denoted by s(P), is the minimal value of s(P;L) where L runs over all linear extensions L of tex2html_wrap_inline3020 . Call a linear extension L of tex2html_wrap_inline3020 optimal iff s(P;L)=s(P). It is a nontrivial fact that optimal linear extensions exist at all. Chapter 9 of [48] is a good general reference.

Let tex2html_wrap_inline3056 be any subset of tex2html_wrap_inline3058 and suppose tex2html_wrap_inline3060 . Write Q for the Boolean layer cake tex2html_wrap_inline3064 . The main result of [24] states that

displaymath3014

Suppose Q is realized as collection of subsets of tex2html_wrap_inline3068 . For tex2html_wrap_inline3070 define tex2html_wrap_inline3072 iff max tex2html_wrap_inline3074 . Then tex2html_wrap_inline3076 is a linear order on Q extending tex2html_wrap_inline3080 (a reverse lexicographic ordering). It is shown in [24] that L is even optimal. The proof rests on a result from extremal set theory which is itself is only accessible - up to now - by methods of multilinear algebra.



Jürg Schmid