### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for MATH 796 at KU 4

### View Full Document

## 14

## 0

## 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

### 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.