Class Note for MATH 796 at KU 10
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 15 views.
Reviews for Class Note for MATH 796 at KU 10
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 229 More on the Characteristic Polynomial De nition 1 Let P be a nite graded poset with rank function r and suppose that n The characteristic polynomial of P is de ned as XPx ZMQQW TW zEP Theorem 1 Let L be a geometric lattice with atoms E Let M be the corresponding matroid on E and r its rank function Then XLx 1 MgtTM1xa0 This was proved last time Example 1 Let G be a simple graph with n vertices and c components so that its graphic matroid MG has rank n E c Let L be the geometric lattice corresponding to M The ats of L are the vertex nanced subgraphs of G the subgraphs H such that if e my E EG and x y are in the same component of H then e E We have seen before that the chromatic polynomial of G is xGh 71 75 he TG 17 h0 Combining this with Theorem 1 we see that XGk ML k so there is not too much inconsistency between these two uses of the symbol x The characteristic polynomial is particularly important in studying hyperplane arrangements coming soon Mobius Functions of Lattices Theorem 2 The Mo39bius function of a geometric lattice alternates in sign Proof Let L be a geometric lattice with atoms E Let M be the corresponding matroid on E and r its rank function Substituting 95 0 in the de nition of the characteristic polynomial and in the formula of Theorem 1 gives ML XL 0 1TMTM10 But TM 1 0 2 0 for every matroid M because TM x y E Nb Meanwhile every interval 0 2 C L is a geometric lattice so the sign of ii 2 is the same as that of 71 2 or zero D In fact more is true the Mobius function of any semimodular not necessarily atomic lattice alternates in sign This can be proven algebraically using tools we re about to develop Stanley Prop 3101 or combinatorially by intepreting 71TMML as enumerating Rlabellings of L see Stanley 3127313 It is easier to compute the Mobius function of a lattice than of an arbitrary poset The main technical tool is the following ring De nition 2 Let L be a lattice The Mobius algebra AL is the vector space of formal Clinear combinations of elements of L with multiplication given by the meet operation So 1 is the multiplicative unit of AL For example if L Q7 then AL Chm 7 x1 x3 7 In general the elements of L form a vector space basis of AL consisting of idempotents since as x x for all x E L It looks like AL could have a complicated structure but actually Proposition 3 AL E ClLl as rings Proof This is just an application of Mobius inversion For as E L de ne Ex ZMy y 3431 By Mobius inversion 1 95 Egg 3431 For as E L let CE be a copy of C with unit 11 so we can identify ClLl with HEB CE De ne a Clinear map lt1 AL A ClLl by Ex gt 11 This is a vector space isomorphism and by 1 we have gtx gty gt 51 gt 5 11 1 11 gtIAy ng 23y ng zgy vaAy so in fact lt1 is a ring isomorphism D The reason the Mobius algebra is useful is that it lets us compute Mx y more easily by summing over a cleverly chosen subset of 9531 rather than the entire interval Proposition 4 Let L be a nite lattice with at least two elements Then for every 1 E L we have 2 Mx 0 ccAa6 Proof On the one hand 151 Eeb 510 by 151 a Mx 2 Mac a xEL xEL Now take the coefficient of D On the other hand A corollary of Proposition 4 is the useful formula 2 ML Mali 7 2 MIX 6 an6 Example 2 Let a E 1 E H Then the partitions as that show up in the sum of are the atoms whose nonsingleton block is i n for some i E n E 1 For each such as the interval 95 1 C H7 is isomorphic to Hn1 so 2 gives MIL 7w IMHH from which it follows by induction that MltHgtlt71gt 1ltn 7 l Wasn t that easy Example 3 Let L L q and let A v1 i i i v E F l v 0 This is a codirnensionl subspace in F2 hence a coatom in Li H X is a nonzero subspace such that X A 0 then X must be a line spanned by some vector 951 i i i 9 With yon y 0 We may as well assume yon l and choose an i i i 95771 arbitrarily so there are 117quot1 such linesi Moreover the interval X C L is isomorphic to L 1qi Therefore Ln4 qquot 1MLn7111 and by induction Mm 47516
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'