Class Note for MATH 796 at KU 4
Popular in Course
Popular in Department
This 4 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 14 views.
Reviews for Class Note for MATH 796 at KU 4
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
Monday 218 The Tutte Polynomial Let M be a matroid with ground set E Recall that we can delete or contract an element e E E to obtain respectively the matroids M E e amd Me on E e whose basis systems are awe B l Be em aw Me Be l B E M e E B Thus deletion is de ned whenever e is not a coloop and contraction is de ned whenever e is not a loop De nition 1 The Tutte polynomial of M is compute recursively as 1 if E Z 1 TMTMxy xTMe ifeisacoloop y TM E e if e is a loop TM E e TMe otherwise for any e E E If M MG is a graphic matroid we may write TG instead of This is more of an algorithm than a de nition and at this point it is not even clear that TM is well de ned because the formula seems to depend on the order in which we pick elements to delete and contract However a miracle occurs it doesn t We will soon prove this by giving a closed formula for TM that does not depend on any such choice In the case that M is a uniform matroid then it is clear at this point that TM is wellde ned by 1 because up to isomorphism M E e and Me are independent of the choices of e E E Example 1 Suppose that M U n that is every element of E is a coloop By induction TMx y x Dually if M E U0n ie every element of E is a loop then TMx y y Example 2 Let M 112 the graphic matroid of the digon two vertices joined by two parallel edges Let e E E then TM TM E e TMe TU1l TUol x y Example 3 Let M E 123 the graphic matroid of K3 as well as the matroid associated with the geometric lattice H3 M5 Applying l for any e E E gives TU23 TU22 TU12 x2xy On the other hand TU13 TU12 TU02 96 y yQ In general we can represent a calculation of TM by a binary tree in which moving down corresponds to deleting or contracting M M e f M ef Me f Mef Example 4 Here is a nonuniform example Let G be the graph below b 1 One possibility is to recurse on edge a or equivalently on b c or d When we delete a the edge 51 becomes a coloop and contracting it produces a copy of K3 Therefore TG7a xx2xy by Example 3 Next apply the recurrence to the edge I in 011 The graph 01171 has a coloop c contracting which produces a digon Meanwhile MGab E 113 Therefore TGa7 b 9595 y and TGab x y yQ Putting it all together we get 0 TG7aTGa TG7aTGa7bTGab xx2xy xxy xyy2 zg2z 2zyxyz E Kl ml xyj N ltD xxy xy9 On the other hand we could have recursed rst on 5 getting TG TG 7 e TGe TG 7 e 7 c TG 7 ec TGe7 c TGec mg x2zy xxy yxy zg2z 2zyxyz g 1gt 0 J x3 x2 xy xxy yxy We can actually see the usefulness of TM even before proving that it is wellde ned Proposition 1 TM 1 1 equals the number of bases of M Proof Let bM TM 11 Then 1 gives 1 if E 2 MM JG 3 ifeisacoloop bge if e is a loop bM 7 e bMe otherwise which is identical to the recurrence for that we observed on Friday 215 D Many other invariants of M can be found in this way by making appropriate substitutions for the indeter minates x y in In particular if we let CM TM 2 2 then 1 if E Z CM 2cG5 if e is a coloop 2cae if e is a loop CM 7 e CMe otherwise so CM 2lEl This suggests that TM ought to have a closed formula as a sum over subsets A Q E with each summand becoming 1 upon setting as 1 and y 17for example with each summand a product of powers of x 7 1 and y 7 1 In fact this is the case Theorem 2 Let r be the Tank function of the mat39mid M Then 2 TW 962 2061TEgt TAgtyiD AHW A93 The quantity rE 7 rA is the comnk of A it is the minimum number of elements one needs to add to A to obtain a spanning set of M Meanwhile A 7 rA is the nullity of A the minimum number of elements one needs to remove from A to obtain an acyclic set Accordingly 2 is referred to as the the comnknullity generating function As an exercise work out TG x y for the graph G of Example 4 you shoudl get the same answer as above Proof of Theorem 2 Let x y denote the generating function on the righthand side of We will prove by induction on n that TM obeys the recurrence 1 for every ground set element e hence equals Let r and r denote the rank functions on M 7 e and Me respectively For the base case if E 3 then 2 gives 1 If e is a 1001 then rA rA rA U 5 for every A C E 5 s0 TM Z x 71rEgt7rAgty 71A7TAgt AgE Z x 71TEgt7TAgty 7 1A7TAgt 7 Z x 71TEgt7TBgty 71A7TBgt A93 1393 egA eEB Z x 71rEe7rAy 7 1A7rA 7 Z x 7 1rEe7rAgty7 1A17rA AgEe AgEe 7 lt1 y 71gt Z x 71gt ltEegt4ltAgtlty 71gt A 4W A Ee 7 e If e is a coloop then 7 HA rA rA U 5 7 1 for every A C E 5 s0 Z x 71TETAy 71WTA AgE Z x 71rEgt7rAgty 7 1A7TAgt 7 Z x 71rEgt7rBgty 71A7TBgt egAgE eeBgE Z x 7 1r Eegt1gt7rAgty7 1A7T Agt AgEe 7 Z x 7 1T Ee1gt7r A1gt y 7 1A17T A1gt AgEe Z x 7 1rEe17rAgty 7 1A7T Agt 7 Z x 7 1T Eegt7r Agty 71A7T Agt AgEe A Ee 95 7171 Z x 71r Eegt7r Agty 71A7T Agt A Ee Finally suppose that e is neither a 1001 nor a coloopi Then rA rA and 7 HA rA U 571 Therefore TQM Z x 71rEgt7rAgty 71A7TAgt AgE Z 96 71TE7TAy71A7TA 7 96 71TE7TAugy 71Aug7rAug AgEe Z 71rEe7rAy 71A7rA 7 71T E17THA1y7 1A17T A71 AgEe Z x 71rEe7rAy 7 D A irA 7 7 Z x 71rEe7rAy 71ATHA AgEe AgEe TM 7 e TMei
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'