18 312 Algebraic Combinatorics Lionel Levine Lecture 7 Lecture date Feb 24 2011 1 Notes by Andrew Geng Partially ordered sets 1 1 Definitions Definition 1 A partially ordered set poset for short is a set P with a binary relation R P P satisfying all of the following conditions 1 reflexivity x x R for all x P 2 antisymmetry x y R and y x R x y 3 transitivity x y R and y z R x z R In analogy with the order on the integers by size we will write x y R as x y or equivalently y x We will use x y to mean that x y and x 6 y When there are multiple posets in play we can disambiguate by using the name of the poset as a subscript e g x P y Remark 2 The word partial indicates that there s no guarantee that all elements can be compared to each other i e we don t know that for all x y P at least one of x y and x y holds A poset in which this is guaranteed is called a totally ordered set Partially ordered sets can be visualized via Hasse diagrams which we now proceed to define Definition 3 Given x y in a poset P the interval x y is the poset z P x z y with the same order as P Definition 4 y covers x means x y x y That is no elements of the poset lie strictly between x and y and x 6 y Definition 5 The Hasse diagram of a partially ordered set P is the directed graph whose vertices are the elements of P and whose edges are the pairs x y for which y covers x It is usually drawn so that elements are placed higher than the elements they cover 7 1 1 2 Examples 1 n handwritten as n is the set n with the usual order on integers 2 The Boolean algebra Bn is the set of subsets of n ordered by inclusion S T means S T Figure 1 Hasse diagrams of B2 and B3 1 2 3 1 2 1 2 3 1 3 1 2 2 1 2 B2 B3 3 3 Dn all divisors of n with d d0 d d0 Figure 2 D12 1 2 3 4 6 12 12 4 6 2 3 1 4 n partitions of n ordered by refinement 1 5 Generalizing Bn any collection P of subsets of a fixed set X is a partially ordered set ordered by inclusion For instance if X is a vector space then we can take P to be the set of all linear subspaces If X is a group we can take P to be the set of all subgroups or the set of all normal subgroups 1 A partition of a set X is a set of disjoint subsets of X whose union is X We say that a partition refines another partition so in the example if every i is a subset of some j i 7 2 2 Maps between partially ordered sets Definition 6 A function f P Q between partially ordered sets is order preserving if x P y f x Q f y Definition 7 Two partially ordered sets P and Q are isomorphic if there exists a bijective order preserving map between them whose inverse is also order preserving Remark 8 For those familiar with topology this should look like the definition of homeomorphic spaces spaces linked by a continuous bijection whose inverse is also continuous A continuous bijection can fail to have a continuous inverse if the topology of the domain has extra open sets and an order preserving bijection between posets can fail to have a continuous inverse if the codomain has extra order information 2 1 Examples 1 D8 4 2 D6 B2 Figure 3 Hasse diagrams of isomorphic posets 3 8 4 4 3 2 2 1 1 1 D8 4 D6 B2 1 2 6 2 3 1 2 Operations on partially ordered sets Given two partially ordered sets P and Q we can define new partially ordered sets in the following ways 7 3 1 Disjoint union P Q is the disjoint union set P t Q where x P Q y if and only if one of the following conditions holds x y P and x P y x y Q and x Q y The Hasse diagram of P Q consists of the Hasse diagrams of P and Q drawn together 2 Ordinal sum P Q is the set P t Q where x P Q y if and only if one of the following conditions holds x P Q y x P and y Q Note that the ordinal sum operation is not commutative In P Q everything in P is less than everything in Q 3 Cartesian product P Q is the Cartesian product set x y x P y Q where x y P Q x0 y 0 if and only if both x P x0 and y Q y 0 The Hasse diagram of P Q is the Cartesian product of the Hasse diagrams of P and Q Example 9 Bn 2 2 z n times Proof Define a candidate isomorphism f 2 2 Bn b1 bn 7 i n bi 2 It s easy to show that f is bijective To check that f and f 1 are order preserving just observe that each of the following conditions is equivalent to the ones that come before and after it b1 bn b01 b0n bi b0i for all i i bi 2 i b0i 2 f b1 bn f b01 b0n 2 Example 10 If k p1 pn is a product of n distinct primes then Dk Bn 7 4 TheQproof of Example 10 is similarly easy using the isomorphism f Dk Bn defined by i S pi 7 S 4 P Q is the set of order preserving maps from Q to P where f P Q g means that f x P g x for all x Q The notation P Q can be motivated by a basic example Example 11 n z P 1 1 k z Q 1 1 nk P Q z 1 1 Perhaps more importantly the following properties hold the proof is the 15th homework problem P Q R P Q P R R P Q P Q R Example 12 The partially ordered set 22 is isomorphic to 3 Proof The order preserving maps are specified by f1 1 f1 2 1 f2 id and f3 1 f3 2 2 so f1 f2 f3 2 4 Graded posets Definition 13 A chain of a partially ordered set P is a totally ordered subset C P i e C x0 x with x0 x The quantity C 1 is its length and is equal to the number of edges in its Hasse diagram Definition 14 A chain is maximal if no other chain strictly contains it Definition 15 The rank of P is the length of the …