18 312 Algebraic Combinatorics Lionel Levine Lecture 11 Lecture date March 15 2011 Today Mobius Algebras Q Notes by Ben Bond n Test The average was 17 If you got 15 you have the option to hand in up to 3 problems from the practice midterm problems 1 7 and 11 for one point each This will raise your score but no higher than 15 This is due by Tuesday March 29 1 Simplicial Complexes Recall last time we proved a formula for the Mobiu s function for a finite poset P Let P 1 P 1 P 0 1 We showed P 0 1 c1 c2 1 r cr where ci 0 x0 x1 xi 1 i e the number of strict chains in P with minimal element 0 maximal element 1 There is something topological in disguise here we make the following definition Definition 1 A simplicial complex on a finite set V is a collection of subsets 2V 2V is the power set of V satisfying 1 x for all x V 2 If F and G F then G Remark 2 2V is a Boolean algebra and is an order ideal that contains all sets x You should think of as a set of generalized triangles glued together as seen in the next example Example 3 Let V a b c d e and a b c d e ab ac bc bd cd ce de abc cde here abc denotes the set a b c Think of each set as a simplex of dimension one less than the cardinality i e corresponds to the diagram below 11 1 The simplicial complex of Example 3 The sets in are described by faces in the diagram The triangles abc cde are shaded because the sets a b c c d e but the set b d e so it does not appear as a shaded triangle in the diagram The two element sets correspond to lines and one element sets correspond to points If there had been a 4 element set it would be drawn as a tetrahedron etc In topology we might have some complicated manifold but by triangulating it we get a simplicial complex and may use combinatorics to better describe it To relate simplicial complexes to posets we make the following definition Definition 4 Given a poset P the order complex of P is the simplicial complex P F P F totally ordered i e P is all chains in P Example 5 Let P B2 P has Hasse diagram 11 2 The Hasse diagram of B2 We see that the maximal chains are a b d and a c d so P contains the sets a b d and a c d The simplicial complex is drawn below the two triangles have been colored differently to emphasize that there are two distinct triangles The Order Complex of B2 Definition 6 The elements F are called faces The dimension of a face is defined as dim F F 1 Remark 7 The definition of dimension corresponds with what we would expect geometrically For example a triangle is defined by its three vertices and has dimension 2 11 3 We now introduce the simplest topological invariant Definition 8 The Euler Characteristic of a simplicial complex is f0 f1 1 d fd Where fi is the number of faces of dimension i and d dim max dimF F Topologically equivalent simplicial complexes give the same value of Notice that the formula for is similar to P seen above In fact Proposition 9 We have P 0 1 P 1 Remark 10 P 1 is known as the reduced Euler characteristic Proof Notice that ck is the number of chains with k 1 elements Since the minimal and maximal elements are 0 and 1 this corresponds to finding elements of P with k 1 elements i e dimension k 2 The number of these is the coefficient fk 2 Thus we have a correspondence between the f values and c values except for there is no f value corresponding to c1 Since c1 1 we must subtract 1 from P to make the two equal 2 2 Mobiu s Algebras Definition 11 Let L be a lattice K a field The Mobiu s Algebra A L is defined as X A L formal sums ax x ax K x L with multiplication x y x y Notice that unlike the incidence algebra the Mobiu s Algebra is commutative Definition 12 We define x X y x x y x 11 4 By Mobiu s inversion we have x X y y x Since x x L form a basis for A L and each x may be written as a linear combination of elements x we see that x x L span A L Since x x L x x L this means x x L form a basis of A L We now take a quick aside to define direct sums of K algebras Definition 13 Let A B be K algebras Their direct sum is A B formal sums a b a A b B Multiplication is given by a b a0 b0 aa0 bb0 Remark 14 Notice A B A B by letting a or b be 0 in the definition of A B Also multiplication can be thought of as letting multiplication from A and B carry over to A B and defining ab 0 for a A b B We now define a map from A L to a direct sum of copies of the field K L Definition 15 In the space x L K let ex denote the identity element of the field in the sum corresponding to index x Then we define M A L K x L such that x ex L The best way to think about x L K is as a vector space with basis ex x L An arbitrary P element is x L cx ex for cx K As an algebra we have multiplication of basis elements ex ey 0 for x 6 y and ex ex ex Multiplication of general vectors follows from this definition for cx dx K X x L cx ex X dx ex x L X cx dx ex x L Proposition 16 The map is an isomporphism of K algebras 11 5 L Proof Since x x L form a basis of A L and ex x L form a basis of x L K and is a linear map giving a bijective correspondence between basis elements we see is an isomorphism of vector spaces To extend this to an isomorphism of algebras we need to check that xy x y for x y A L although is defined in terms of x it is easiest to check multiplication in the basis x x L Using the formula for x given after Definition 12 we get X X X ez z z xy x y z x y z x y z x y The last two equalities come from linearity of and the definition of We now evalutate x y This gives X X X x …