Class Note for MATH 796 at KU
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 16 views.
Reviews for Class Note for MATH 796 at KU
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 11808 Posets De nition A partially ordered set or poset is a set P equipped with a relation 3 that is re exive antisymmetric and transitive That is for all x y 2 E P l x S x re exivity 2 If x S y amd y S x then x y antisymmetry 3 If x S y and y S 2 then x S 2 transitivity We ll usually assume that P is nite Example 1 Boolean algebras Let 1 2 n a standard piece of notation in combinatorics and let Q7 be the power set of We can partially order Q7 by writing S S T if S Q T 123 12 13 23 N A Y The rst two pictures are Hasse diagrams They don t include all relations just the covering relations which are enough to generate all the relations in the poset As you can see on the right including all the relations would make the diagram unnecessarily complicated De nitions Let P be a poset and z y E P o x is covered by y written 95 lt y if x lt y and there exists no 2 such that x lt 2 lt y o The interval from x to y is xy2 P 953233 This is nonempty if and only if x S y and it is a singleton set if and only if x The Boolean algebra Q7 has a unique minimum element namely 3 and a unique maximum element namely Not every poset has to have such elements but if a poset does we ll call them 0 and 1 respectively De nition A poset that has both a O and a l is called bounded An element that covers 0 is called an atom and an element that is covered by l is called a coatorn For example the atoms in Q7 are the singleton subsets of De nition A subset C C P is called a Chain if its elements are pairwise comparable It is called an antichain or clutter if its elements are pairwise incomparable 123 123 123 gt 4 3949 1 2 1 2 1 2 3 1 2 1 chain antichain antichain neither Ranked Posets One of the many nice properties of n is that its elements fall nicely into horizontal slices sorted by their cardinalities Whenever S lt T it is the case that lTl 5 1 A poset for which we can do this is called a ranked poset However we can t de ne ranked in this way because it is tautological Instead De nition A poset is ranked if every maximal chain has the same cardinality A poset is graded if it is ranked and bounded If P is a graded poset its rank function r P A N is de ned as Mac length of any chain from O to 95 Here length measures the number of steps not the number of elements 7 ice edges rather than vertices in the Hasse diagrami Note Maximal chain and maximum chain are not synonyms Maximal means not contained in any other while maximum means of greatest possible size Every maximum chain is certainly maximal but not necessarily vice versaithat s precisely what it means for a poset to be ranked An easy consequence of the de nition is that if x lt y then My Mac 1 proof left to the reader De nition Let P be a ranked poset with rank function r The rankgenerating function of P is the formal power series FPII Z a xeP Thus for each k the coefficient of qlC is the number of elements at rank k We can now say that the Boolean algebra is ranked by cardinality In particular Fae Z 11 1 11 Sch Of course if you expand this polynomial out it is palindromic because the coefficients are a row of Pascal s Triangle That is 7 is ranksymmetric In fact much more is true For any poset P we can de ne the dual poset Pquot by reversing all the order relations or equivalently turning the Hasse diagram upside down It s not hard to prove that the Boolean algebra is selfdual ices 7 E Q from which it immediately follows that it is ranksymmetric The following is a nonranked poset an important example to have around called N5 Example 2 The partition lattice Let ll be the poset of all set partitions of E g two elements of H5 are S 134 2 5 abbr S 134l25 T l3 4 25 abbr T 13l4l25 The sets 134 and 25 are called the blocks of S We can impose a partial order on Hn by putting T S S if every block of T is contained in a block of S for short T re nes S 1234 123 123M 124m 134m 234m 12 34 13 24 1423 ampMV39 lt t v gtVr 12w 1 23 13m 1234 13W 23m4 1423 24MB 34m2 2 3 1l2l3l4 o The covering relations are of the form merge two blocks into one o H is graded With 0 1 2 n and l 12 n The rank function is MS n7 o The coef cients of the rankgenerating function of H are the Stirling numbers of the second kind Sn k number of partitions of into k blocks That is Fnq FHJQ 2301 Mamet k1 For example F301 1 Sq q2 and F401 1 6q 7112 q
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'