18 312 Algebraic Combinatorics Lionel Levine Lecture 9 Lecture date March 3 2011 1 1 1 Notes by Damien Jiang Order preserving maps from posets to chains Order preserving maps from n to m We begin with a question Question 1 How many order preserving maps are there from the n chain n to the m chain m m n N Equivalently what is mn In an order preserving map f from n to m intervals of n are mapped to elements of m Let ai be the number of j n with f j i i m The set of ai uniquely determine f since f preserve order So we have reduced the question to the following equivalent problem Question 2 How many solutions in non negative integers a1 a2 am are there of the equation a1 a2 am n A solution to this equation is known as a composition of n rather than a partition since the order of the ai matters So we would like to know how many compositions n m of n are there into m nonnegative parts n m 1 n 2 3 m But this means n m 1 We have n m x 1 x x m 1 n m n m m n 1 a coincidence No since we can use a standard m n bijection here often known as Stars and Bars or Balls and Walls Each composition of n into m parts is equivalent to placing n stars in a line and separating them with m 1 n m 1 bars Hence the number of compositions of n into m parts is We can also m 1 get an immediate bijection between m n 1 and n m 1 by swapping the stars and bars This leads us to ask the following 9 1 Question 3 Are m 1 n and n 1 m isomorphic as posets We already showed that the number of maps n m 1 from n to m 1 is equal to the number of maps m n 1 from m to n 1 But it is also true that m 1 n n 1 m because m 1 n 2m n 2m n 2n m n 1 m Moreover all of these are isomorphic to J m n 1 2 Order preserving maps from P to m Now we consider the more general case of order preserving maps from a finite poset P to m Lemma 4 Order preserving maps f P m Multichains 0 I0 Im 1 in J P Proof Given f P m define Ii f 1 1 2 i This is an order ideal of P since if x Ii and y x then f x i f y f x i y Ii This provides the desired bijection 2 Lemma 5 Surjective order preserving maps f P m Chains 0 I0 Im 1 in J P Proof Again consider Ii as defined above we only need to show that the inequalities are now strict But now since f is surjective there exists x with f x i 1 so x Ii 1 but x Ii Hence Ii 1 Ii 2 9 2 2 Linear extensions Definition 6 Let P be a poset with P n A linear extension of P is an order preserving bijection from P to n Alternatively a linear extension of P is a labeling of the elements of P with a distinct inger from 1 through n such that a s label is smaller than that of b if a b For example consider the following Hasse diagram of a linear extension of P 3 3 Figure 1 Example A linear extension of 3 3 9 7 8 4 5 3 6 2 1 Define e P linear extensions of P Then from the section before we have e P linear extensions of P surjective order preserving maps from P n bijective order preserving maps from P n since P n chains 0 I0 Im 1 in J P by Lemma 5 maximal chains in J P since rank J P n Next are a few examples Example 7 maximal chains in m n We have m n 2m 1 2n 1 2m 1 n 1 m n J m 1 n 1 9 3 so maximal chains in m n linear extensions of m 1 n 1 e m 1 n 1 m n 2 m 1 Example 8 maximal chains in boolean algebra Bn Since Bn J 1 1 z 1 the number of maximal chains in Bn is e 1 1 1 n n 3 3 1 Incidence algebras Definitions Let P be a finite poset and K a finite field We will usually take K C Definition 9 Int P intervals x y P x y The empty set is not an interval Definition 10 The incidence algebra I P of a poset P is the vector space of all functions f Int P K I P has multiplication f g x y P x z y f x z g z y An equivalent really the dual definition of I P is the following Definition 11 I P is the P x y Int P f x y x y set of formal linear combinations of intervals with multiplication x w y z x y z w 0 otherwise 9 4 1 We can check that X f x y x y X x y z w Int P X g z w z w z w Int P x y Int P X f x y g z w x y z w z 0 unless y z f x y g y w x w x y w X f x y g y z x w x w Int P Another equivalent definition involves matrices Let the elements of P be x1 xn Then Definition 12 I P n n matrices A aij K aij 0 unless xi xj So each interval xi xj with xi xj is represented as the matrix eij with just one nonzero entry aij Example 13 P n Then I P is the set of upper triangular n n matrices 0 Example 14 P B2 Then I P looks like 0 0 element of K 3 2 0 0 0 0 where denotes a nonzero and 1 more chain counting Two important elements of I P are the zeta element and the identity 1 Definition 15 x y 1 x y Int P Example 16 2 x y X x z z y x y Int P x z y 9 5 Example 17 k Y X k x y X zi 1 zi x z0 zk y i 1 1 x z0 zk y so k x y multichains x z0 z1 zk y Definition 18 1 x y xy 1 0 x y otherwise 0 x y Now consider 1 I P we have 1 x y So 1 x 6 y X 1 k x y 1 zi 1 zi x z0 zk y which counts precisely the number of chains x z0 z1 zk y Using this result …