Class Note for MATH 796 at KU 8
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 21 views.
Reviews for Class Note for MATH 796 at KU 8
Report this Material
What is Karma?
Karma is the currency of StudySoup.
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