Class Note for MATH 796 at KU 5
Popular in Course
Popular in Department
This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 14 views.
Reviews for Class Note for MATH 796 at KU 5
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Friday 12508 Lattices De nition A poset L is a lattice if every nite subset of x y E L have a unique m x y and E x yi That is xymaxzEL l 23mg xVyminzEL l 22xyi Note that eg 95 y x if and only if x S y These operations are commutative and associative so for any nite M C L theAmeet M and join VM are wellde ned elements of L In particular every nite lattice is bounded with 0 L and 1 VL Proposition 1 Absorption laws LetL be a lattice and z y E L Then xVzy x and xzy z Proof left to the reader Proposition 2 Let P be a poset that is a meetsemilattice ie every nonempty B Q P has a wellde ned meet AB and has a 1 Then P is a lattice ie every nite nonempty subset ofP has a wellde ned join Proof Let A Q P and let B b E P l b 2 a for all a E A Note that B y ll because 1 E El I claim that B is the unique least upper bound for At First we have B 2 a for all a E A by de nition of B and of meeti Second if x 2 a for all a E A then x E B and so 95 2 AB proving the claimi D De nition 1 Let L be a lattice A sublattice of L is a subposet L C L that a is a lattice and b inherits its meet and join operations from L That is for all x y E L we have xALyxLy and xVLyxLyi Example 1 The subspace lattice Let q be a prime power let qu be the eld of order q and let V F a vector space of dimension n over qu The subspace lattice LVq L q is the set of all vector subspaces of V ordered by inclusion We could replace qu with any old eld if you don t mind in nite posetsi The meet and join operations on L q are given by W W W O W and W W W W i We could construct analogous posets by ordering the normal subgroups of a group or the prime ideals of a ring or the submodules of a module by inclusion However these posets are not necessarily ranked while L q is ranked by dimension The simplest example is when 11 2 and n 2 so that V 0 0 0 1 l 0 l Of course V has one subspace of dimension 2 itself and one of dimension 0 the zero spacei Meanwhile it has three subspaces of dimension 1 each consists of the zero vector and one nonzero vectori Therefore L22 E M5i Note that L q is selfdual under the antiautomorphism W A Wt An antiautomorphism is an isomor phism P A P3 Example 2 Bruhat order and weak Bruhat order Let 37 be the set of permutations of ice the symmetric groupi Write elements of 37 as strings 7102 an of distinct digits eg 47182635 E 63 lmpose a partial order on 37 de ned by the following covering relations 1 a lt 7 if 7 can be obtained by swapping 71 with 7111 where 71 lt 7111 For example 4718E35 lt 4718 35 and 4 82635 gt 4 82635 2 a lt 7 if 7 can be obtained by swapping a with 7 wherez39 lt j and aj a 1 For example 47182635 lt 47183625 If we only use the rst kind of covering relation we obtain the weak Bruhat order 321 321 312 231 312 231 132 213 132 213 123 123 Bruhat order Weak Bruhat order The Bruhat order is not in general a lattice while the weak order is although this fact is nontrivial By the way we could replace 6 with any Coxeter group although that s a whole nother semester Both posets are graded and selfdual and have the same rank function namely the number of inversions r0 The rankgenerating function is a very nice polynomial called the qfactorial ij liltjand 71 gt01 11 F641111q1qqQ1qqquot 1H12 11 Distributive Lattices De nition A lattice L is distributive if the following two equivalent conditions hold xszxyxz Vxy2 L xVyzxVyxz Vxy2 L Proving that these conditions are equivalent is not too hard but is not trivial it s a homework problem 1 The Boolean algebra n is a distributive lattice because the settheoretic operations of union and intersection are distributive over each other 2 M5 and N5 are not distributive U N5 M5 aVcbb xVy22 llbVllCll ac2yz0 In particular the partition lattice H7 is not distributive for n 2 3 recall that H3 E M5 3 Any sublattice of a distributive lattice is distributive In particular Young s lattice Y is distributive because it is locally a sublattice of 7 4 The set D7 of all positive integer divisors of a xed integer 71 ordered by divisibility is a distributive lattice proof for homework De nition Let P be a poset An order ideal of P is a set A Q P that is closed under going down ie if x E A and y S x then y E A The poset of all order ideals of P ordered by containment is denoted JPi The order ideal generated by 951 i i i 957 E P is the smallest order ideal containing them namely x1iiix gt yEP l nyl for somei By the way there is a natural bijection between JP and the set of antichains of P since the maximal elements of any order ideal A form an antichain that generates it abcd P JP Proposition The operations A B A U B and A B A O B make JP into a distributive lattice partially ordered by set containment Sketch of proof All you have to do is check that A U B and A O B are in fact order ideals of P Then JP is just a sublattice of the Boolean algebra on P D
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'