×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

21

0

4

# Class Note for MATH 796 at KU 8

Marketplace > Kansas > Class Note for MATH 796 at KU 8

No professor available

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
No professor available
TYPE
Class Notes
PAGES
4
WORDS
KARMA
25 ?

## 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 21 views.

×

## Reviews for Class Note for MATH 796 at KU 8

×

×

### What is Karma?

#### 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 222 The Chromatic Polynomial Let G E be a graph A hcolo39ring ofG is a function f V 7gt h the coloring is proper if y whenever vu E E The chromatic function of G is de ned as xG h of proper colorings of G Theorem 1 Let G be a graph with n vertices and c components Let 20 h 71 ichCTG 17 h0l Then 20 h xG h Proof First we show that the chromatic function satis es the recurrence 1 MG kkquot ifEZl 2 XG k 0 if G has a loop 3 XG k k 1XG5 k if e is a coloop 4 xG h xG 7 e h 7 xGe h otherwise If E 3 then every one of the h colorings of G is proper and if G has a loop then it has no proper colorings so 1 and 2 are easy Suppose e gay is not a loop Let f be a proper hcoloring of G 7 e If then we can identify as and y to obtain a proper hcoloring of Ge lf y then f is a proper hcoloring of G So 4 follows This argument applies even if e is a coloop In that case however the component H of G containing e becomes two components H and H of G 7 e whose colorings can be chosen independently of each other So the probability that in any proper coloring is lh implying A corollary by induction on lVl is that xG h is a polynomial in h and thus has the right to be called the chromatic polynomial of 0 The graph G 7 e has n vertices and either c l or c components according as e is or is not a coloop Meanwhile Ge has n 7 1 vertices and c components By the recursive de nition of the Tutte polynomial 540 k 71quot CkCTG 1430 h if E ll 7 0 if e is a loop 7 l 7 h7l 1 ChCTGe l7 h 0 if e is a coloop 71 Chc TG 7 e l7 h 0 TGe l7 h 0 otherwise h if E ll 7 0 if e is a loop 7 h 7 1XGe h if e is a coloop xG 7 e h 7 xGe h otherwise which is exactly the recurrence satis ed by the chromatic polynomial This proves the theorem D This result raises the question of what this specialization of TM means in the case that M is a an arbitrary not necessarily graphic matroid Stay tuned Acyclic Orientations An orientation D of a graph G E is an assignment of a direction to each edge my E E either y or A directed cycle is a sequence x0 x1 1 i i 95771 of vertices such that 95195244 is a directed edge for every 239 Here the indices are taken modulo An orientation is acyclic if it has no directed cycles Let AG be the set of acyclic orientations of G and let 11G Theorem 2 Stanley 1973 For every graph G on n vertices we have 10 TG12071n71XG171 Proof The second equality is a consequence of Theorem 1 Plugging ac 2 and y 0 into the De nition of the Tutte polynomial we obtain the recurrence we need to establish in order to prove the rst equality A1 If E ll then 1G 1 A23 If e E E is a loop then 10 0 A2b If e E E is a coloop then 10 211Ge A3 If e E E is neither a loop nor a coloop then 10 1G E e 1Ge A1 holds because the number of orientations of G is 2lVl and any orientation of a forest in particular an edgelesss graph is acyclic For A23 note that if G has a loop then it cannot possibly have an acyclic orientation If G has a coloop e then e doesn t belong to any cycle of C so any acyclic orientation of Ge can be extended to an acyclic orientation of G by orienting e in either direction proving A2b The trickiest part is A3 Fix an edge e my E For each orientation D ofG let D be the orientation produced by reversing the direction of e and let A1 D e AG D e AG A2 D e AG D g AGt Clearly 10 lA1llA2li Let D be an acyclic orientation of G E e If D has a path from ac to y for short an ac ypath then it cannot have a y acpath so directing e as y but not e 335 produces an acyclic orientation of G all this is true if we reverse the roles of ac and y We get every orientation in A2 in this way On the other hand if D does not have either an ac ypath or a y xpath then we can orient e in either direction to produce an orientation in A1 Therefore 5 am 7e 3M Aal Now let D be an acyclic orientation of Ge and let D be the corresponding acyclic orientation of G E e 1 claim that D can be extended to an acyclic orientation of G by orienting e in either way Indeed if it were impossible to orient e as fy then the reason would have to be that D contained a path from y to ac but y and ac are the same vertex in D and D wouldn t be acyclic Therefore there is a bijection between AGe and matched pairs D in AG so 1 6 l195 ilAll Now combining 5 and 6 proves A3 D Some other related graphtheoretic invariants you can nd from the Tutte polynomial o The number of totally cyclic orientations ie orientations in which every edge belongs to a directed cycle HW problem 0 The flow polynomial of G whose value at k is the number of edgelabelings f E A k 7 1 such that the sum at every vertex is 0 mod k 0 The reliability polynomial the probability that the graph remains connected if each edge is deleted with independent probability p o The enhanced chromatic polynomial which enumerates all qcolorings by improper edges g 3 Z tryEE l frfy frVelq This is essentially Crapo s cobounda39ry polynomial and provides the same information as the Tutte polynomial 0 And more the canonical source for all things Tutte is T Brylawski and J Oxley The Tutte polynomial and its applications Chapter 6 of Matpoid applications N White editor Cambridge Univ Press 1992 Basis Activities We know that TM ac y has nonnegative integer coefficients and that TM l l is the number of bases of M These observations suggest that we should be able to interpret the Tutte polynomial as a generating function for bases that is there should be combinatorially de ned functions i e A N such that 7 TMxy Z avian BX BEM In fact this is the case The tricky part is that and 53 must be de ned with respect to a total order on the ground set E so they are not really invariants of B itself However another miracle occurs the righthand side of 7 does not depend on this choice of total order lndex the ground set of E as 51 e and totally order the elements of E by their subscripts De nition 1 Let B be a basis of M 0 Let c E B The fundamental cocircuit Cez B is the unique cocircuit in E B U 51 That is Cel B Ej l BelU Ej E We say that 51 is internally active with respect to B if 51 is the minimal element of Cel B 0 Let c E B The fundamental circuit Cez B is the unique circuit in B U 51 That is CelB Ej l B5jU 51 E We say that 51 is externally active with respect to B if 51 is the minimal element of Cel B 0 Finally we let 53 and denote respectively the number of externally active and internally active elements with respect to B Here s an example Let G be the graph with edges labeled as shown below and let B be the spanning tree 52 54 55 shown in red The middle gure shows Cel B and the righthand gure shows Cquot 55 B e2 e4 93 Then C51B 51 54 55 so 51 is externally active Ces B 52 53 55 so 53 is not externally active Therefore eB 1 Meanwhile Ceg B 52 63 so el is internally active Ce4 B 51 54 so 63 is not internally active C55 B 51 53 55 so 53 is not internally active Therefore 1 Theorem 3 Let M be a matmid on E Fix a total ordering of E and de ne 239e A N as above Then 7 holds Thus in the example above the spanning tree B would contribute the monomial my xlyl to TG x The proof which I ll omit is just a matter of bookkeeping It s a matter of showing that the generating function on the righthand side of 7 satis es the recursive de nition of the Tutte polynomial

×

×

### BOOM! Enjoy Your Free Notes!

×

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

Jim McGreen Ohio University

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

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

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

Become an Elite Notetaker and start selling your notes online!
×

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