Ch.9: The Tutte polynomial

Chapter 9 of the book "Matroids: A Geometric Introduction" by Gary Gordon and Jennifer McNulty (2012) 9.1. Motivation and history 9.2. Definition and basic examples 9.3. Corank–nullity polynomial 9.4. Duality and direct sum 9.5. Tutte–Grothendieck invariants 9.6. The chromatic polynomial

104 flashcards · Mathematics · by lakesare

Part of Textbooks › Matroids: A Geometric Introduction (Gordon, McNulty) · 9 courses

1. [Motivation and history] What does the Four Color Theorem say (in its original form, about maps)?

   The regions of every map can be colored with at most 4 colors so that no two regions sharing a border receive the same color. Asked by Francis Guthrie in an 1852 letter to his brother Frederick; proved by Appel and Haken in 1976.

2. [Motivation and history] Why was Appel and Haken's 1976 proof of the Four Color Theorem noteworthy?

   It settled an old conjecture It resolved, in the affirmative, a conjecture that had been open for 125 years. It used a computer essentially It was the first significant mathematical proof that made essential use of a computer: more than 1000 hours of computer time for checking cases. A later, streamlined proof checks far fewer cases, but still needs a computer.

3. [Motivation and history] How is coloring the regions of a map turned into coloring the vertices of a graph?

   Color the vertices of the geometric dual of the map's planar graph: each region becomes a vertex, and regions sharing a border become adjacent vertices. The map itself is a planar graph: its edges are the boundaries, its vertices the points where two or more boundaries meet.

4. [Motivation and history] A coloring of the vertices of a graph is proper if no two adjacent vertices receive the same color.

5. [Motivation and history] What does the chromatic polynomial χ(G;λ)\chi(G; \lambda)χ(G;λ) of a graph GGG count?

   The number of proper colorings of GGG using λ\lambdaλ (or fewer) colors. Introduced by G. D. Birkhoff in 1912 to attack the Four Color Problem; χ(G;λ)\chi(G; \lambda)χ(G;λ) turns out to be a polynomial in λ\lambdaλ .Example: for K2K_2K2​ (one edge), χ(K2;λ)=λ(λ−1)\chi(K_2; \lambda) = \lambda(\lambda - 1)χ(K2​;λ)=λ(λ−1) : λ\lambdaλ choices for one end, λ−1\lambda - 1λ−1 for the other. So χ(K2;2)=2\chi(K_2; 2) = 2χ(K2​;2)=2 .

6. [Motivation and history] Theorem 9.1 (the Four Color Theorem via the chromatic polynomial) Let GGG be a planar graph. Then … ?

   χ(G;4)>0\boldsymbol{\chi(G; 4) > 0}χ(G;4)>0 At least one proper coloring of GGG with 4 colors exists.

7. [Motivation and history] How could the chromatic polynomial χ(G;λ)\chi(G; \lambda)χ(G;λ) prove the Four Color Theorem, and has this worked?

   By analytic study of the location of the roots of χ(G;λ)\chi(G; \lambda)χ(G;λ) for planar graphs GGG . No proof has arisen this way. The chromatic polynomial generalizes to a two-variable polynomial of matroids: the Tutte polynomial.

8. [Motivation and history] What did William Tutte (born 1917, England) do during WWII, and which contribution to matroid theory does the book single out?

   Cryptanalysis at Bletchley Park (decoding the FISH messages); foundational work on excluded minors. After the war he did a doctorate in mathematics at Cambridge without formal mathematics training. He published some 168 papers and books.

9. [Definition and basic examples] An isthmus of a matroid MMM is an element in every basis; a loop is an element in no basis. M−eM - eM−e is the deletion, M/eM/eM/e the contraction of eee .How is the Tutte polynomial t(M;x,y)t(M; x, y)t(M;x,y) of a matroid MMM on ground set EEE defined?

   eee neither an isthmus nor a loop t(M;x,y)=t(M−e;x,y)+t(M/e;x,y)t(M; x, y) = t(M - e; x, y) + t(M/e; x, y)t(M;x,y)=t(M−e;x,y)+t(M/e;x,y) Example: t(U1,2)=t(U1,1)+t(U0,1)=x+yt(U_{1,2}) = t(U_{1,1}) + t(U_{0,1}) = x + yt(U1,2​)=t(U1,1​)+t(U0,1​)=x+y . eee an isthmus t(M;x,y)=x⋅t(M/e;x,y)t(M; x, y) = x \cdot t(M/e; x, y)t(M;x,y)=x⋅t(M/e;x,y) Example: t(U1,1)=x⋅t(empty matroid)=xt(U_{1,1}) = x \cdot t(\text{empty matroid}) = xt(U1,1​)=x⋅t(empty matroid)=x . eee a loop t(M;x,y)=y⋅t(M−e;x,y)t(M; x, y…

10. [Definition and basic examples] The Tutte polynomial is defined recursively: t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) if eee is neither an isthmus nor a loop; t(M)=x⋅t(M/e)t(M) = x \cdot t(M/e)t(M)=x⋅t(M/e) if eee is an isthmus; t(M)=y⋅t(M−e)t(M) = y \cdot t(M - e)t(M)=y⋅t(M−e) if eee is a loop; t(M)=1t(M) = 1t(M)=1 if E=∅E = \emptysetE=∅ .What are the four matroids on two elements, and their Tutte polynomials?

    U2,2U_{2,2}U2,2​ : two isthmuses t=x2t = x^2t=x2 Contract each isthmus: x⋅x⋅1x \cdot x \cdot 1x⋅x⋅1 . U1,1⊕U0,1U_{1,1} \oplus U_{0,1}U1,1​⊕U0,1​ : an isthmus and a loop t=xyt = xyt=xy Contract the isthmus ( xxx ), delete the loop ( yyy ). U1,2U_{1,2}U1,2​ : a double point t=x+yt = x + yt=x+y Delete aaa : an isthmus ( xxx ). Contract aaa : a loop ( yyy ). U0,2U_{0,2}U0,2​ : two loops t=y2t = y^2t=y2 Delete each loop: y⋅y⋅1y \cdot y \cdot 1y⋅y⋅1 .

11. [Definition and basic examples] The Tutte polynomial is defined recursively: t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) if eee is neither an isthmus nor a loop; t(M)=x⋅t(M/e)t(M) = x \cdot t(M/e)t(M)=x⋅t(M/e) if eee is an isthmus; t(M)=y⋅t(M−e)t(M) = y \cdot t(M - e)t(M)=y⋅t(M−e) if eee is a loop; t(M)=1t(M) = 1t(M)=1 if E=∅E = \emptysetE=∅ . U1,2U_{1,2}U1,2​ is a double point on E={a,b}E = \{a, b\}E={a,b} . Why is t(U1,2;x,y)=x+yt(U_{1,2}; x, y) = x + yt(U1,2​;x,y)=x+y ?

    aaa is neither a loop nor an isthmus, and U1,2−aU_{1,2} - aU1,2​−a is an isthmus ( xxx ) while U1,2/aU_{1,2}/aU1,2​/a is a loop ( yyy ). So t(U1,2)=t(U1,2−a)+t(U1,2/a)=x+yt(U_{1,2}) = t(U_{1,2} - a) + t(U_{1,2}/a) = x + yt(U1,2​)=t(U1,2​−a)+t(U1,2​/a)=x+y .

12. [Definition and basic examples] When computing t(M;x,y)t(M; x, y)t(M;x,y) by the deletion–contraction recursion, does the order in which elements are deleted and contracted matter?

    No: every order gives the same polynomial, so t(M;x,y)t(M; x, y)t(M;x,y) is well defined. The proof shows t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) , where sss is the corank–nullity polynomial, a sum over all subsets that involves no choices.

13. [Definition and basic examples] The Tutte polynomial is defined recursively: t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) if eee is neither an isthmus nor a loop; t(M)=x⋅t(M/e)t(M) = x \cdot t(M/e)t(M)=x⋅t(M/e) if eee is an isthmus; t(M)=y⋅t(M−e)t(M) = y \cdot t(M - e)t(M)=y⋅t(M−e) if eee is a loop; t(M)=1t(M) = 1t(M)=1 if E=∅E = \emptysetE=∅ .Compute the Tutte polynomial of the three-point line U2,3U_{2,3}U2,3​ by deleting and contracting aaa .

    t(U2,3;x,y)=x2+x+y\boldsymbol{t(U_{2,3}; x, y) = x^2 + x + y}t(U2,3​;x,y)=x2+x+y U2,3−a=U2,2U_{2,3} - a = U_{2,2}U2,3​−a=U2,2​ (two isthmuses, x2x^2x2 ) and U2,3/a=U1,2U_{2,3}/a = U_{1,2}U2,3​/a=U1,2​ (a double point, x+yx + yx+y ).

14. [Definition and basic examples] The Tutte polynomial is defined recursively: t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) if eee is neither an isthmus nor a loop; t(M)=x⋅t(M/e)t(M) = x \cdot t(M/e)t(M)=x⋅t(M/e) if eee is an isthmus; t(M)=y⋅t(M−e)t(M) = y \cdot t(M - e)t(M)=y⋅t(M−e) if eee is a loop; t(M)=1t(M) = 1t(M)=1 if E=∅E = \emptysetE=∅ .Compute t(U1,3;x,y)t(U_{1,3}; x, y)t(U1,3​;x,y) and then t(U2,4;x,y)t(U_{2,4}; x, y)t(U2,4​;x,y) .

    t(U1,3)=x+y+y2\boldsymbol{t(U_{1,3}) = x + y + y^2}t(U1,3​)=x+y+y2 , t(U2,4)=x2+2x+2y+y2\ \boldsymbol{t(U_{2,4}) = x^2 + 2x + 2y + y^2} t(U2,4​)=x2+2x+2y+y2 U1,3−e=U1,2U_{1,3} - e = U_{1,2}U1,3​−e=U1,2​ ( x+yx + yx+y ) and U1,3/e=U0,2U_{1,3}/e = U_{0,2}U1,3​/e=U0,2​ ( y2y^2y2 ). U2,4−e=U2,3U_{2,4} - e = U_{2,3}U2,4​−e=U2,3​ ( x2+x+yx^2 + x + yx2+x+y ) and U2,4/e=U1,3U_{2,4}/e = U_{1,3}U2,4​/e=U1,3​ ( x+y+y2x + y + y^2x+y+y2 ).

15. [Definition and basic examples] The Tutte polynomial is defined recursively: t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) if eee is neither an isthmus nor a loop; t(M)=x⋅t(M/e)t(M) = x \cdot t(M/e)t(M)=x⋅t(M/e) if eee is an isthmus; t(M)=y⋅t(M−e)t(M) = y \cdot t(M - e)t(M)=y⋅t(M−e) if eee is a loop; t(M)=1t(M) = 1t(M)=1 if E=∅E = \emptysetE=∅ .Compute t(U3,4;x,y)t(U_{3,4}; x, y)t(U3,4​;x,y) and t(U1,4;x,y)t(U_{1,4}; x, y)t(U1,4​;x,y) .

    t(U3,4)=x3+x2+x+y\boldsymbol{t(U_{3,4}) = x^3 + x^2 + x + y}t(U3,4​)=x3+x2+x+y , t(U1,4)=x+y+y2+y3\ \boldsymbol{t(U_{1,4}) = x + y + y^2 + y^3} t(U1,4​)=x+y+y2+y3 U3,4−e=U3,3U_{3,4} - e = U_{3,3}U3,4​−e=U3,3​ ( x3x^3x3 ) and U3,4/e=U2,3U_{3,4}/e = U_{2,3}U3,4​/e=U2,3​ ( x2+x+yx^2 + x + yx2+x+y ). U1,4−e=U1,3U_{1,4} - e = U_{1,3}U1,4​−e=U1,3​ ( x+y+y2x + y + y^2x+y+y2 ) and U1,4/e=U0,3U_{1,4}/e = U_{0,3}U1,4​/e=U0,3​ ( y3y^3y3 ).

16. [Definition and basic examples] In this computation of the Tutte polynomial of a rank 4 matroid MMM (7 points), each box stands for the Tutte polynomial of the matroid inside; the circled point is deleted (left arrow) and contracted (right arrow). Why does the box U1,2⊕U1,2U_{1,2} \oplus U_{1,2}U1,2​⊕U1,2​ (two double points) carry the factor (2+x)(2 + x)(2+x) ?

    It arises three times: twice by deleting or contracting a non-loop non-isthmus (factor 1), once by contracting an isthmus (factor xxx ). The isthmus is the single point in the rank 3 box with two double points, after the circled point there is deleted.

17. [Definition and basic examples] The deletion–contraction tree of a rank 4 matroid MMM on 7 points ends in the matroids U3,4U_{3,4}U3,4​ with factor (1+x)(1 + x)(1+x) , U1,2⊕U1,2U_{1,2} \oplus U_{1,2}U1,2​⊕U1,2​ with factor (2+x)(2 + x)(2+x) , and U1,4U_{1,4}U1,4​ with factor 1. What is t(M;x,y)t(M; x, y)t(M;x,y) ?

    x4+3x3+4x2+2x+2x2y+5xy+2y+xy2+3y2+y3\boldsymbol{x^4 + 3x^3 + 4x^2 + 2x + 2x^2y + 5xy + 2y + xy^2 + 3y^2 + y^3}x4+3x3+4x2+2x+2x2y+5xy+2y+xy2+3y2+y3 (1+x)(x3+x2+x+y)+(2+x)(x+y)2+(x+y+y2+y3)(1 + x)(x^3 + x^2 + x + y) + (2 + x)(x + y)^2 + (x + y + y^2 + y^3)(1+x)(x3+x2+x+y)+(2+x)(x+y)2+(x+y+y2+y3) , using t(U1,2⊕U1,2)=t(U1,2)2=(x+y)2t(U_{1,2} \oplus U_{1,2}) = t(U_{1,2})^2 = (x + y)^2t(U1,2​⊕U1,2​)=t(U1,2​)2=(x+y)2 .

18. [Corank–nullity polynomial] What is the corank–nullity polynomial (or rank generating polynomial) s(M;u,v)s(M; u, v)s(M;u,v) of a matroid MMM on EEE with rank function rrr ?

    s(M;u,v)=∑A⊆Eur(E)−r(A) v∣A∣−r(A)\boldsymbol{\displaystyle s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} \, v^{|A| - r(A)}}s(M;u,v)=A⊆E∑​ur(E)−r(A)v∣A∣−r(A) Example: an isthmus E={e}E = \{e\}E={e} , r(E)=1r(E) = 1r(E)=1 : A=∅A = \emptysetA=∅ gives u1v0u^1 v^0u1v0 , A=EA = EA=E gives u0v0u^0 v^0u0v0 , so s=u+1s = u + 1s=u+1 .

19. [Corank–nullity polynomial] For A⊆EA \subseteq EA⊆E in a matroid with rank function rrr , what are the corank and the nullity of AAA ?

    Corank =r(E)−r(A)= r(E) - r(A)=r(E)−r(A) , nullity =∣A∣−r(A)= |A| - r(A)=∣A∣−r(A) . Both terms are borrowed from linear algebra. Corank 0 means AAA is spanning; nullity 0 means AAA is independent.Example: in U2,3U_{2,3}U2,3​ on {a,b,c}\{a, b, c\}{a,b,c} , A={a}A = \{a\}A={a} has corank 1 and nullity 0; A=EA = EA=E has corank 0 and nullity 1.

20. [Corank–nullity polynomial] The corank–nullity polynomial of a matroid MMM on EEE with rank function rrr is s(M;u,v)=∑A⊆Eur(E)−r(A) v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} \, v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) . MMM on E={a,b,c,d}E = \{a, b, c, d\}E={a,b,c,d} is the three-point line abcabcabc together with an isthmus ddd (rank 3). What is s(M;u,v)s(M; u, v)s(M;u,v) ?

    s(M;u,v)=u3+4u2+6u+uv+3+v\boldsymbol{s(M; u, v) = u^3 + 4u^2 + 6u + uv + 3 + v}s(M;u,v)=u3+4u2+6u+uv+3+v ∅\emptyset∅ : u3u^3u3 . Each of the 4 points: u2u^2u2 . Each of the 6 pairs (all independent, rank 2): uuu . abcabcabc (rank 2, nullity 1): uvuvuv . abdabdabd , acdacdacd , bcdbcdbcd (bases): 111 each. EEE (rank 3, nullity 1): vvv .

21. [Corank–nullity polynomial] What is a matroid invariant?

    A function f:M→Rf : \mathcal{M} \to Rf:M→R from the class M\mathcal{M}M of all matroids to a commutative ring RRR such that M1≅M2M_1 \cong M_2M1​≅M2​ implies f(M1)=f(M2)f(M_1) = f(M_2)f(M1​)=f(M2​) . Example: the number of bases is a matroid invariant, and so is the corank–nullity polynomial s(M;u,v)s(M; u, v)s(M;u,v) .

22. [Corank–nullity polynomial] Theorem 9.9. How is the Tutte polynomial t(M;x,y)t(M; x, y)t(M;x,y) obtained from the corank–nullity polynomial s(M;u,v)s(M; u, v)s(M;u,v) ? The corank–nullity polynomial of a matroid MMM on EEE with rank function rrr is s(M;u,v)=∑A⊆Eur(E)−r(A) v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} \, v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) .

    t(M;x,y)=s(M;x−1,y−1)\boldsymbol{t(M; x, y) = s(M; x - 1, y - 1)}t(M;x,y)=s(M;x−1,y−1) In particular, t(M;x,y)t(M; x, y)t(M;x,y) is a well-defined matroid invariant.Example: an isthmus has s=u+1s = u + 1s=u+1 , and s(x−1,y−1)=x=ts(x - 1, y - 1) = x = ts(x−1,y−1)=x=t .

23. [Corank–nullity polynomial] t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) , where s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) is the corank–nullity polynomial.Why does this equation show that the recursively defined Tutte polynomial is well defined and a matroid invariant?

    s(M;u,v)s(M; u, v)s(M;u,v) is defined without any choices, from the rank function alone. So ttt equals one fixed polynomial for every order of deletions and contractions, and isomorphic matroids (same rank function up to relabeling) get the same one.

24. [Corank–nullity polynomial] M=U1,1⊕U2,3M = U_{1,1} \oplus U_{2,3}M=U1,1​⊕U2,3​ (a three-point line abcabcabc and an isthmus ddd ) has s(M;u,v)=u3+4u2+6u+uv+3+vs(M; u, v) = u^3 + 4u^2 + 6u + uv + 3 + vs(M;u,v)=u3+4u2+6u+uv+3+v , and t(M1⊕M2)=t(M1) t(M2)t(M_1 \oplus M_2) = t(M_1) \, t(M_2)t(M1​⊕M2​)=t(M1​)t(M2​) .What is t(M;x,y)t(M; x, y)t(M;x,y) , and does it equal s(M;x−1,y−1)s(M; x - 1, y - 1)s(M;x−1,y−1) ?

    t(M;x,y)=x3+x2+xy\boldsymbol{t(M; x, y) = x^3 + x^2 + xy}t(M;x,y)=x3+x2+xy , and yes, s(M;x−1,y−1)s(M; x - 1, y - 1)s(M;x−1,y−1) equals it. t(M)=x⋅(x2+x+y)t(M) = x \cdot (x^2 + x + y)t(M)=x⋅(x2+x+y) . (x−1)3+4(x−1)2+6(x−1)+(x−1)(y−1)+3+(y−1)(x - 1)^3 + 4(x - 1)^2 + 6(x - 1) + (x - 1)(y - 1) + 3 + (y - 1)(x−1)3+4(x−1)2+6(x−1)+(x−1)(y−1)+3+(y−1) : the xxx -terms 3x−8x+6x−x3x - 8x + 6x - x3x−8x+6x−x cancel, the constants −1+4−6+1+3−1-1 + 4 - 6 + 1 + 3 - 1−1+4−6+1+3−1 cancel, leaving x3+x2+xyx^3 +…

25. [Corank–nullity polynomial] Claim: t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) , where s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) .The proof is by induction on ∣E∣|E|∣E∣ . How does it check the base case ∣E∣=1|E| = 1∣E∣=1 ?

    Isthmus: s=u+1s = u + 1s=u+1 , so s(x−1,y−1)=x=ts(x - 1, y - 1) = x = ts(x−1,y−1)=x=t . Loop: s=v+1s = v + 1s=v+1 , so s(x−1,y−1)=y=ts(x - 1, y - 1) = y = ts(x−1,y−1)=y=t . For a loop, r(E)=0r(E) = 0r(E)=0 : A=EA = EA=E gives u0v1u^0 v^1u0v1 and A=∅A = \emptysetA=∅ gives u0v0u^0 v^0u0v0 .

26. [Corank–nullity polynomial] Claim: t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) , where s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) . Proof by induction on ∣E∣|E|∣E∣ .In the inductive step, e∈Ee \in Ee∈E is neither an isthmus nor a loop. What is the plan?

    Show s(M;u,v)=s(M−e;u,v)+s(M/e;u,v)s(M; u, v) = s(M - e; u, v) + s(M/e; u, v)s(M;u,v)=s(M−e;u,v)+s(M/e;u,v) , then apply induction to M−eM - eM−e and M/eM/eM/e and the recursion t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) . t(M)=t(M−e)+t(M/e)=s(M−e;x−1,y−1)+s(M/e;x−1,y−1)=s(M;x−1,y−1)t(M) = t(M - e) + t(M/e) = s(M - e; x - 1, y - 1) + s(M/e; x - 1, y - 1) = s(M; x - 1, y - 1)t(M)=t(M−e)+t(M/e)=s(M−e;x−1,y−1)+s(M/e;x−1,y−1)=s(M;x−1,y−1) .

27. [Corank–nullity polynomial] MMM has rank function rrr and e∈Ee \in Ee∈E is not a loop. How are the rank functions r′r'r′ of M−eM - eM−e and r′′r''r′′ of M/eM/eM/e given by rrr ?

    Deletion: r′(A)=r(A)r'(A) = r(A)r′(A)=r(A) for A⊆E−eA \subseteq E - eA⊆E−e . Contraction: r′′(A−e)=r(A)−1r''(A - e) = r(A) - 1r′′(A−e)=r(A)−1 for e∈Ae \in Ae∈A . Example: U2,3U_{2,3}U2,3​ on {a,b,c}\{a, b, c\}{a,b,c} , e=ae = ae=a : r′′({b})=r({a,b})−1=1r''(\{b\}) = r(\{a, b\}) - 1 = 1r′′({b})=r({a,b})−1=1 .

28. [Corank–nullity polynomial] s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) ; eee is not a loop, and r′′r''r′′ is the rank function of M/eM/eM/e , with r′′(A−e)=r(A)−1r''(A - e) = r(A) - 1r′′(A−e)=r(A)−1 for e∈Ae \in Ae∈A .Why is the sum of the terms over the sets AAA containing eee equal to s(M/e;u,v)s(M/e; u, v)s(M/e;u,v) ?

    A↦A−eA \mapsto A - eA↦A−e is a bijection onto the subsets of E−eE - eE−e that keeps the corank and the nullity, because r(E)r(E)r(E) , r(A)r(A)r(A) and ∣A∣|A|∣A∣ all drop by exactly 1. r(E)−r(A)=r′′(E−e)−r′′(A−e)r(E) - r(A) = r''(E - e) - r''(A - e)r(E)−r(A)=r′′(E−e)−r′′(A−e) and ∣A∣−r(A)=∣A−e∣−r′′(A−e)|A| - r(A) = |A - e| - r''(A - e)∣A∣−r(A)=∣A−e∣−r′′(A−e) .

29. [Corank–nullity polynomial] s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) ; eee is not an isthmus, and r′r'r′ is the rank function of M−eM - eM−e .Why is the sum of the terms over the sets AAA avoiding eee equal to s(M−e;u,v)s(M - e; u, v)s(M−e;u,v) ?

    r(A)=r′(A)r(A) = r'(A)r(A)=r′(A) , and r(E)=r′(E−e)r(E) = r'(E - e)r(E)=r′(E−e) because eee is not an isthmus, so each term is the same term of s(M−e;u,v)s(M - e; u, v)s(M−e;u,v) . Together with the sets containing eee (which give s(M/e)s(M/e)s(M/e) ), this proves s(M)=s(M−e)+s(M/e)s(M) = s(M - e) + s(M/e)s(M)=s(M−e)+s(M/e) .

30. [Corank–nullity polynomial] Claim: t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) , where s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) . Inductive step.When eee is an isthmus, why is s(M;u,v)=(u+1) s(M/e;u,v)s(M; u, v) = (u + 1) \, s(M/e; u, v)s(M;u,v)=(u+1)s(M/e;u,v) ?

    Sets containing eee give s(M/e)s(M/e)s(M/e) ; for sets AAA avoiding eee , the nullity stays the same but the corank is 1 larger than in M/eM/eM/e , giving u⋅s(M/e)u \cdot s(M/e)u⋅s(M/e) . Contracting an isthmus keeps r(A)r(A)r(A) for e∉Ae \notin Ae∈/A but r(E)=r′′(E−e)+1r(E) = r''(E - e) + 1r(E)=r′′(E−e)+1 . Then u+1=xu + 1 = xu+1=x , matching t(M)=x⋅t(M/e)t(M) = x \cdot t(M/e)t(M)=x⋅t(M/e) .

31. [Corank–nullity polynomial] Claim: t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) , where s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) . Inductive step.When eee is a loop, why is s(M;u,v)=(v+1) s(M−e;u,v)s(M; u, v) = (v + 1) \, s(M - e; u, v)s(M;u,v)=(v+1)s(M−e;u,v) ?

    Sets avoiding eee give s(M−e)s(M - e)s(M−e) ; for sets AAA containing eee , the corank of AAA equals that of A−eA - eA−e but the nullity is 1 larger, giving v⋅s(M−e)v \cdot s(M - e)v⋅s(M−e) . A loop adds nothing to the rank: r(A)=r(A−e)r(A) = r(A - e)r(A)=r(A−e) , while ∣A∣=∣A−e∣+1|A| = |A - e| + 1∣A∣=∣A−e∣+1 . Then v+1=yv + 1 = yv+1=y , matching t(M)=y⋅t(M−e)t(M) = y \cdot t(M - e)t(M)=y⋅t(M−e) .

32. [Corank–nullity polynomial] t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) , where s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) .What do t(M;1,1)t(M; 1, 1)t(M;1,1) , t(M;2,1)t(M; 2, 1)t(M;2,1) , t(M;1,2)t(M; 1, 2)t(M;1,2) and t(M;2,2)t(M; 2, 2)t(M;2,2) count? In the examples, MMM is the three-point line abcabcabc plus an isthmus ddd , with t(M;x,y)=x3+x2+xyt(M; x, y) = x^3 + x^2 + xyt…

    t(M;1,1)=s(M;0,0)t(M; 1, 1) = s(M; 0, 0)t(M;1,1)=s(M;0,0) The number of bases of MMM . Example: t(1,1)=1+1+1=3t(1, 1) = 1 + 1 + 1 = 3t(1,1)=1+1+1=3 (bases abdabdabd , acdacdacd , bcdbcdbcd ). t(M;2,1)=s(M;1,0)t(M; 2, 1) = s(M; 1, 0)t(M;2,1)=s(M;1,0) The number of independent sets of MMM . Example: t(2,1)=8+4+2=14t(2, 1) = 8 + 4 + 2 = 14t(2,1)=8+4+2=14 . t(M;1,2)=s(M;0,1)t(M; 1, 2) = s(M; 0, 1)t(M;1,2)=s(M;0,1) The number of spanning sets of MMM . Example: t(1,2)=1+1+2=4t(1, 2) = 1 + 1 + 2 = 4t(…

33. [Corank–nullity polynomial] t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) , where s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) (with 00=10^0 = 100=1 ).Why does s(M;0,0)s(M; 0, 0)s(M;0,0) equal the number of bases of MMM ?

    A term 0r(E)−r(A)0∣A∣−r(A)0^{r(E) - r(A)} 0^{|A| - r(A)}0r(E)−r(A)0∣A∣−r(A) is 1 exactly when r(A)=r(E)r(A) = r(E)r(A)=r(E) ( AAA spanning) and ∣A∣=r(A)|A| = r(A)∣A∣=r(A) ( AAA independent), i.e. when AAA is a basis; otherwise it is 0.

34. [Corank–nullity polynomial] s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) (with 00=10^0 = 100=1 ).Why does s(M;1,0)s(M; 1, 0)s(M;1,0) count the independent sets and s(M;0,1)s(M; 0, 1)s(M;0,1) the spanning sets?

    In s(M;1,0)s(M; 1, 0)s(M;1,0) a term is 1 exactly when the nullity ∣A∣−r(A)|A| - r(A)∣A∣−r(A) is 0 ( AAA independent); in s(M;0,1)s(M; 0, 1)s(M;0,1) exactly when the corank r(E)−r(A)r(E) - r(A)r(E)−r(A) is 0 ( AAA spanning). And s(M;1,1)s(M; 1, 1)s(M;1,1) adds 1 for every subset, giving 2∣E∣2^{|E|}2∣E∣ .

35. [Corank–nullity polynomial] The Tutte polynomial is defined recursively: t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) if eee is neither an isthmus nor a loop; t(M)=x⋅t(M/e)t(M) = x \cdot t(M/e)t(M)=x⋅t(M/e) if eee is an isthmus; t(M)=y⋅t(M−e)t(M) = y \cdot t(M - e)t(M)=y⋅t(M−e) if eee is a loop; t(M)=1t(M) = 1t(M)=1 if E=∅E = \emptysetE=∅ .How does induction on ∣E∣|E|∣E∣ show that t(M;1,1)t(M; 1, 1)t(M;1,1) is the number b(M)b(M)b(M) of bases?

    bbb satisfies the same recursion at x=y=1x = y = 1x=y=1 : b(M)=b(M−e)+b(M/e)b(M) = b(M - e) + b(M/e)b(M)=b(M−e)+b(M/e) if eee is neither isthmus nor loop, b(M)=b(M/e)b(M) = b(M/e)b(M)=b(M/e) if eee is an isthmus, b(M)=b(M−e)b(M) = b(M - e)b(M)=b(M−e) if eee is a loop. An isthmus lies in every basis and a loop in none. Base case: a single isthmus or loop has t=xt = xt=x or yyy , value 1 at (1,1)(1, 1)(1,1) , and one basis.Example: b(U2,3)=b(U2,2)+b(U1,2)=1+2=3b(U_{2,3}) = b(U_{2,2}) + b(U_{1,2})…

36. [Corank–nullity polynomial] Can two non-isomorphic matroids have the same Tutte polynomial?

    Yes. M1M_1M1​ has a four-point line and M2M_2M2​ does not, so M1≇M2M_1 \not\cong M_2M1​≅M2​ , yet t(M1)=t(M2)t(M_1) = t(M_2)t(M1​)=t(M2​) .

37. [Corank–nullity polynomial] Why do M1M_1M1​ and M2M_2M2​ have the same Tutte polynomial?

    M1−x≅M2−yM_1 - x \cong M_2 - yM1​−x≅M2​−y and M1/x≅M2/yM_1/x \cong M_2/yM1​/x≅M2​/y , and x,yx, yx,y are neither loops nor isthmuses, so t(M1)=t(M1−x)+t(M1/x)=t(M2−y)+t(M2/y)=t(M2)t(M_1) = t(M_1 - x) + t(M_1/x) = t(M_2 - y) + t(M_2/y) = t(M_2)t(M1​)=t(M1​−x)+t(M1​/x)=t(M2​−y)+t(M2​/y)=t(M2​) .

38. [Corank–nullity polynomial] Two non-isomorphic matroids M1M_1M1​ , M2M_2M2​ have the same Tutte polynomial: M1M_1M1​ (rank 3) has a four-point line; M2M_2M2​ is graphic.Which properties of a matroid does this show the Tutte polynomial cannot determine?

    Being graphic, and being binary. M2M_2M2​ is graphic, but M1M_1M1​ is not even binary: it has the four-point line U2,4U_{2,4}U2,4​ . Any property one has and the other lacks is not determined by ttt . M1M_1M1​ and M2M_2M2​ also have different numbers of circuits, flats and hyperplanes.

39. [Duality and direct sum] Theorem 9.12. How is the Tutte polynomial of the dual matroid M∗M^*M∗ obtained from t(M;x,y)t(M; x, y)t(M;x,y) ?

    t(M∗;x,y)=t(M;y,x)\boldsymbol{t(M^*; x, y) = t(M; y, x)}t(M∗;x,y)=t(M;y,x) Swap xxx and yyy .Example: U2,3∗=U1,3U_{2,3}^* = U_{1,3}U2,3∗​=U1,3​ , and t(U2,3)=x2+x+yt(U_{2,3}) = x^2 + x + yt(U2,3​)=x2+x+y , t(U1,3)=y2+y+xt(U_{1,3}) = y^2 + y + xt(U1,3​)=y2+y+x .Example: two loops U0,2=U2,2∗U_{0,2} = U_{2,2}^*U0,2​=U2,2∗​ : t=y2t = y^2t=y2 and x2x^2x2 .

40. [Duality and direct sum] The dual rank function is r∗(A)=r(E−A)+∣A∣−r(E)r^*(A) = r(E - A) + |A| - r(E)r∗(A)=r(E−A)+∣A∣−r(E) .What are the corank and the nullity of AAA in M∗M^*M∗ , in terms of MMM ?

    Corank of AAA in M∗M^*M∗ = nullity of E−AE - AE−A in MMM ; nullity of AAA in M∗M^*M∗ = corank of E−AE - AE−A in MMM . r∗(E)−r∗(A)=∣E−A∣−r(E−A)r^*(E) - r^*(A) = |E - A| - r(E - A)r∗(E)−r∗(A)=∣E−A∣−r(E−A) and ∣A∣−r∗(A)=r(E)−r(E−A)|A| - r^*(A) = r(E) - r(E - A)∣A∣−r∗(A)=r(E)−r(E−A) .

41. [Duality and direct sum] t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) with s(M;u,v)=∑A⊆Eur(E)−r(A)v∣A∣−r(A)s(M; u, v) = \sum_{A \subseteq E} u^{r(E) - r(A)} v^{|A| - r(A)}s(M;u,v)=∑A⊆E​ur(E)−r(A)v∣A∣−r(A) . The corank of AAA in M∗M^*M∗ is the nullity of E−AE - AE−A in MMM , and vice versa.How does this prove t(M∗;x,y)=t(M;y,x)t(M^*; x, y) = t(M; y, x)t(M∗;x,y)=t(M;y,x) ?

    Substituting A′=E−AA' = E - AA′=E−A turns s(M∗;u,v)s(M^*; u, v)s(M∗;u,v) into ∑A′⊆Eu∣A′∣−r(A′)vr(E)−r(A′)=s(M;v,u)\sum_{A' \subseteq E} u^{|A'| - r(A')} v^{r(E) - r(A')} = s(M; v, u)∑A′⊆E​u∣A′∣−r(A′)vr(E)−r(A′)=s(M;v,u) . Then t(M∗;x,y)=s(M∗;x−1,y−1)=s(M;y−1,x−1)=t(M;y,x)t(M^*; x, y) = s(M^*; x - 1, y - 1) = s(M; y - 1, x - 1) = t(M; y, x)t(M∗;x,y)=s(M∗;x−1,y−1)=s(M;y−1,x−1)=t(M;y,x) .

42. [Duality and direct sum] Theorem 9.13. What is the Tutte polynomial of a direct sum M1⊕M2M_1 \oplus M_2M1​⊕M2​ ?

    t(M1⊕M2;x,y)=t(M1;x,y) t(M2;x,y)\boldsymbol{t(M_1 \oplus M_2; x, y) = t(M_1; x, y) \, t(M_2; x, y)}t(M1​⊕M2​;x,y)=t(M1​;x,y)t(M2​;x,y) Example: t(U1,1⊕U0,1)=x⋅yt(U_{1,1} \oplus U_{0,1}) = x \cdot yt(U1,1​⊕U0,1​)=x⋅y .Example: three-point line plus an isthmus: t(U2,3⊕U1,1)=(x2+x+y)⋅xt(U_{2,3} \oplus U_{1,1}) = (x^2 + x + y) \cdot xt(U2,3​⊕U1,1​)=(x2+x+y)⋅x .

43. [Duality and direct sum] Proposition 9.14. M1,M2M_1, M_2M1​,M2​ are matroids on disjoint ground sets E1,E2E_1, E_2E1​,E2​ , and e∈E1e \in E_1e∈E1​ . What are (M1⊕M2)−e(M_1 \oplus M_2) - e(M1​⊕M2​)−e and (M1⊕M2)/e(M_1 \oplus M_2)/e(M1​⊕M2​)/e ?

    (M1⊕M2)−e=(M1−e)⊕M2\boldsymbol{(M_1 \oplus M_2) - e = (M_1 - e) \oplus M_2}(M1​⊕M2​)−e=(M1​−e)⊕M2​ and (M1⊕M2)/e=(M1/e)⊕M2\boldsymbol{(M_1 \oplus M_2)/e = (M_1/e) \oplus M_2}(M1​⊕M2​)/e=(M1​/e)⊕M2​ Similarly for e∈E2e \in E_2e∈E2​ .

44. [Duality and direct sum] The Tutte polynomial is defined recursively: t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) if eee is neither an isthmus nor a loop; t(M)=x⋅t(M/e)t(M) = x \cdot t(M/e)t(M)=x⋅t(M/e) if eee is an isthmus; t(M)=y⋅t(M−e)t(M) = y \cdot t(M - e)t(M)=y⋅t(M−e) if eee is a loop; t(M)=1t(M) = 1t(M)=1 if E=∅E = \emptysetE=∅ . (M1⊕M2)−e=(M1−e)⊕M2(M_1 \oplus M_2) - e = (M_1 - e) \oplus M_2(M1​⊕M2​)−e=(M1​−e)⊕M2​ and (M1⊕M2)/e=(M1/e)⊕M2(M_1 \oplus M_2)/e = (M_1/e) \oplu…

    Base ∣E1∣=1|E_1| = 1∣E1​∣=1 : eee is a loop or isthmus, so t(M)=y⋅t(M2)t(M) = y \cdot t(M_2)t(M)=y⋅t(M2​) or x⋅t(M2)x \cdot t(M_2)x⋅t(M2​) . Step: t(M)=t(M1−e)t(M2)+t(M1/e)t(M2)=t(M1)t(M2)t(M) = t(M_1 - e) t(M_2) + t(M_1/e) t(M_2) = t(M_1) t(M_2)t(M)=t(M1​−e)t(M2​)+t(M1​/e)t(M2​)=t(M1​)t(M2​) . Here M=M1⊕M2M = M_1 \oplus M_2M=M1​⊕M2​ ; the step uses the deletion and contraction formulas and induction for M1−eM_1 - eM1​−e and M1/eM_1/eM1​/e . If eee is a loop or isthmus, the step is similar.

45. [Duality and direct sum] What are the two ways to prove facts about the Tutte polynomial?

    Induction From the deletion–contraction recursion defining t(M;x,y)t(M; x, y)t(M;x,y) . Example: t(M;1,1)t(M; 1, 1)t(M;1,1) is the number of bases, since the number of bases satisfies the same recursion. Subset expansion From t(M;x,y)=s(M;x−1,y−1)t(M; x, y) = s(M; x - 1, y - 1)t(M;x,y)=s(M;x−1,y−1) , a sum over all subsets A⊆EA \subseteq EA⊆E . Example: t(M∗;x,y)=t(M;y,x)t(M^*; x, y) = t(M; y, x)t(M∗;x,y)=t(M;y,x) , by replacing each AAA with E−AE - AE−A .

46. [Duality and direct sum] What is the beta invariant β(M)\beta(M)β(M) of a matroid MMM with Tutte polynomial t(M;x,y)=∑bi,jxiyjt(M; x, y) = \sum b_{i,j} x^i y^jt(M;x,y)=∑bi,j​xiyj ?

    β(M)=b1,0\boldsymbol{\beta(M) = b_{1,0}}β(M)=b1,0​ , the coefficient of xxx . Example: t(U2,4)=x2+2x+2y+y2t(U_{2,4}) = x^2 + 2x + 2y + y^2t(U2,4​)=x2+2x+2y+y2 , so β(U2,4)=2\beta(U_{2,4}) = 2β(U2,4​)=2 .

47. [Duality and direct sum] The Tutte polynomial is defined recursively: t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) if eee is neither an isthmus nor a loop; t(M)=x⋅t(M/e)t(M) = x \cdot t(M/e)t(M)=x⋅t(M/e) if eee is an isthmus; t(M)=y⋅t(M−e)t(M) = y \cdot t(M - e)t(M)=y⋅t(M−e) if eee is a loop; t(M)=1t(M) = 1t(M)=1 if E=∅E = \emptysetE=∅ .Why is β(M)≥0\beta(M) \ge 0β(M)≥0 (the coefficient of xxx in t(M;x,y)t(M; x, y)t(M;x,y) ) for every matroid MMM ?

    All coefficients of t(M;x,y)t(M; x, y)t(M;x,y) are nonnegative: the recursion starts from 1 and only adds polynomials and multiplies by xxx or yyy .

48. [Duality and direct sum] Proposition 9.16. eee is neither an isthmus nor a loop of MMM . How is β(M)\beta(M)β(M) (the coefficient of xxx in the Tutte polynomial) given by minors?

    β(M)=β(M/e)+β(M−e)\boldsymbol{\beta(M) = \beta(M/e) + \beta(M - e)}β(M)=β(M/e)+β(M−e) Take the coefficient of xxx in t(M)=t(M−e)+t(M/e)t(M) = t(M - e) + t(M/e)t(M)=t(M−e)+t(M/e) .Example: β(U2,4)=β(U2,3)+β(U1,3)=1+1=2\beta(U_{2,4}) = \beta(U_{2,3}) + \beta(U_{1,3}) = 1 + 1 = 2β(U2,4​)=β(U2,3​)+β(U1,3​)=1+1=2 .

49. [Duality and direct sum] Proposition 9.17. MMM is a matroid that is not a loop. When is MMM connected, in terms of β(M)\beta(M)β(M) (the coefficient of xxx in the Tutte polynomial)?

    MMM is connected if and only if β(M)>0\beta(M) > 0β(M)>0 . Example: t(U2,3)=x2+x+yt(U_{2,3}) = x^2 + x + yt(U2,3​)=x2+x+y , β=1\beta = 1β=1 : connected.Example: t(U2,3⊕U1,1)=x3+x2+xyt(U_{2,3} \oplus U_{1,1}) = x^3 + x^2 + xyt(U2,3​⊕U1,1​)=x3+x2+xy , β=0\beta = 0β=0 : not connected.

50. [Duality and direct sum] MMM not a loop: MMM is connected if and only if β(M)>0\beta(M) > 0β(M)>0 , where β(M)\beta(M)β(M) is the coefficient of xxx in t(M;x,y)t(M; x, y)t(M;x,y) .Why must a single loop be excluded?

    A single loop is connected, but t=yt = yt=y , so β=0\beta = 0β=0 .

51. [Duality and direct sum] The beta invariant β(M)\beta(M)β(M) of a matroid MMM is the coefficient b1,0b_{1,0}b1,0​ of xxx in its Tutte polynomial t(M;x,y)=∑bi,jxiyjt(M; x, y) = \sum b_{i,j} x^i y^jt(M;x,y)=∑bi,j​xiyj . All bi,j≥0b_{i,j} \ge 0bi,j​≥0 . t(M1⊕M2)=t(M1) t(M2)t(M_1 \oplus M_2) = t(M_1) \, t(M_2)t(M1​⊕M2​)=t(M1​)t(M2​) , and b0,0=0b_{0,0} = 0b0,0​=0 for every matroid with nonempty ground set.Why does β(M)>0\beta(M) > 0β(M)>0 imply that MMM is connected?

    If M=M1⊕M2M = M_1 \oplus M_2M=M1​⊕M2​ (both nonempty), then every term of t(M1) t(M2)t(M_1)\,t(M_2)t(M1​)t(M2​) has degree at least 2, so the coefficient of xxx is 0. A term b1,0xb_{1,0}xb1,0​x of the product would need one factor to contribute a constant, but b0,0=0b_{0,0} = 0b0,0​=0 for both factors, and no coefficients are negative, so nothing cancels.Example: U2,2=U1,1⊕U1,1U_{2,2} = U_{1,1} \oplus U_{1,1}U2,2​=U1,1​⊕U1,1​ has t=x⋅x=x2t = x \cdot x = x^2t=x⋅x=x2 , so β(U2,2)=0\beta(U_{2,2})…

52. [Duality and direct sum] The beta invariant β(M)\beta(M)β(M) of a matroid MMM is the coefficient b1,0b_{1,0}b1,0​ of xxx in its Tutte polynomial t(M;x,y)=∑bi,jxiyjt(M; x, y) = \sum b_{i,j} x^i y^jt(M;x,y)=∑bi,j​xiyj . All bi,j≥0b_{i,j} \ge 0bi,j​≥0 .For eee neither a loop nor an isthmus, β(M)=β(M/e)+β(M−e)\beta(M) = \beta(M/e) + \beta(M - e)β(M)=β(M/e)+β(M−e) . For a connected MMM and any eee , M−eM - eM−e or M/eM/eM/e is connected.How does the proof show β(M)>0\beta(M) > 0β(M)>0 for every conn…

    Induction on ∣E∣|E|∣E∣ : one of M−eM - eM−e , M/eM/eM/e is connected and not a loop, so it has β>0\beta > 0β>0 , and the other has β≥0\beta \ge 0β≥0 . Base cases: an isthmus has t=xt = xt=x , β=1\beta = 1β=1 ; the double point U1,2U_{1,2}U1,2​ (the only connected matroid on 2 elements) has t=x+yt = x + yt=x+y , β=1\beta = 1β=1 .Example: U2,3U_{2,3}U2,3​ : β=β(U1,2)+β(U2,2)=1+0=1\beta = \beta(U_{1,2}) + \beta(U_{2,2}) = 1 + 0 = 1β=β(U1,2​)+β(U2,2​)=1+0=1 , matching t=x2+x+yt = x^2 + x + yt=x2+x+…

53. [Duality and direct sum] Proof that a connected matroid MMM (not a loop) has β(M)>0\beta(M) > 0β(M)>0 : induction on ∣E∣|E|∣E∣ , using β(M)=β(M/e)+β(M−e)\beta(M) = \beta(M/e) + \beta(M - e)β(M)=β(M/e)+β(M−e) and that M−eM - eM−e or M/eM/eM/e is connected.Why does the induction need ∣E∣=2|E| = 2∣E∣=2 as a base case, not only ∣E∣=1|E| = 1∣E∣=1 ?

    For ∣E∣=2|E| = 2∣E∣=2 , the connected minor can be a single loop, which has β=0\beta = 0β=0 . For ∣E∣>2|E| > 2∣E∣>2 , M−eM - eM−e and M/eM/eM/e have at least 2 elements, so neither is a single loop.Example: the double point U1,2U_{1,2}U1,2​ : U1,2/eU_{1,2}/eU1,2​/e is a loop, β=0\beta = 0β=0 , and U1,2−eU_{1,2} - eU1,2​−e is an isthmus, β=1\beta = 1β=1 .

54. [Duality and direct sum] Theorem 9.18 (Merino, de Mier, Noy, 2001) Let MMM be a matroid with Tutte polynomial t(M;x,y)t(M; x, y)t(M;x,y) . Then t(M;x,y)t(M; x, y)t(M;x,y) is irreducible in Z[x,y]\mathbb{Z}[x, y]Z[x,y] if and only if … ?

    MMM is connected. If M=M1⊕M2M = M_1 \oplus M_2M=M1​⊕M2​ is not connected, then t(M)=t(M1) t(M2)t(M) = t(M_1)\,t(M_2)t(M)=t(M1​)t(M2​) factors. The converse is much harder: it needs a detailed analysis of the terms.Example: t(U2,2)=x⋅xt(U_{2,2}) = x \cdot xt(U2,2​)=x⋅x factors; t(U2,3)=x2+x+yt(U_{2,3}) = x^2 + x + yt(U2,3​)=x2+x+y is irreducible.

55. [Tutte–Grothendieck invariants] b(M)b(M)b(M) , i(M)i(M)i(M) and sp(M)sp(M)sp(M) are the numbers of bases, independent sets and spanning sets of a matroid MMM . Which recursion do all three satisfy, for eee neither an isthmus nor a loop?

    f(M)=f(M−e)+f(M/e)\boldsymbol{f(M) = f(M - e) + f(M/e)}f(M)=f(M−e)+f(M/e) Deletion–contraction, the same recursion as the Tutte polynomial.Example: U2,3U_{2,3}U2,3​ has 3 bases, and b(U2,3−e)+b(U2,3/e)=b(U2,2)+b(U1,2)=1+2b(U_{2,3} - e) + b(U_{2,3}/e) = b(U_{2,2}) + b(U_{1,2}) = 1 + 2b(U2,3​−e)+b(U2,3​/e)=b(U2,2​)+b(U1,2​)=1+2 .

56. [Tutte–Grothendieck invariants] What does the (imprecise) meta-theorem about the Tutte polynomial say?

    Any matroid invariant fff with f(M)=f(M−e)+f(M/e)f(M) = f(M - e) + f(M/e)f(M)=f(M−e)+f(M/e) can be obtained from the Tutte polynomial. A meta-theorem is a statement about a collection of theorems. Brylawski's theorem on Tutte–Grothendieck invariants is the precise version.Example: the number of bases is b(M)=t(M;1,1)b(M) = t(M; 1, 1)b(M)=t(M;1,1) .

57. [Tutte–Grothendieck invariants] What are the four conditions on a function fff from (isomorphism classes of) matroids to Z[x,y]\mathbb{Z}[x, y]Z[x,y] for fff to be a Tutte–Grothendieck (T-G) invariant? ( III = the one-element matroid that is an isthmus, LLL = the one-element matroid that is a loop.)

    Invariance f(M1)=f(M2)f(M_1) = f(M_2)f(M1​)=f(M2​) whenever M1≅M2M_1 \cong M_2M1​≅M2​ . Example: the cycle matroid of a triangle and three collinear points (both U2,3U_{2,3}U2,3​ ) have the same i=7i = 7i=7 . Deletion–contraction f(M)=f(M−e)+f(M/e)f(M) = f(M - e) + f(M/e)f(M)=f(M−e)+f(M/e) if eee is neither a loop nor an isthmus. Example: i(U2,3)=7=i(U2,2)+i(U1,2)=4+3i(U_{2,3}) = 7 = i(U_{2,2}) + i(U_{1,2}) = 4 + 3i(U2,3​)=7=i(U2,2​)+i(U1,2​)=4+3 (independent sets). Isthmus rule f(M)=f(I)⋅f(M/e…

58. [Tutte–Grothendieck invariants] Theorem 9.19 (Brylawski) Let fff be a Tutte–Grothendieck invariant ( fff is a matroid invariant, f(M)=f(M−e)+f(M/e)f(M) = f(M - e) + f(M/e)f(M)=f(M−e)+f(M/e) for eee neither a loop nor an isthmus, f(M)=f(I)⋅f(M/e)f(M) = f(I) \cdot f(M/e)f(M)=f(I)⋅f(M/e) for an isthmus eee , f(M)=f(L)⋅f(M−e)f(M) = f(L) \cdot f(M - e)f(M)=f(L)⋅f(M−e) for a loop eee , where III and LLL are the one-element isthmus and loop). Then f(M)= ?f(M) = \; ?f(M)=?

    f(M)=t(M;f(I),f(L))\boldsymbol{f(M) = t(M; f(I), f(L))}f(M)=t(M;f(I),f(L)) Evaluate the Tutte polynomial at x=f(I)x = f(I)x=f(I) , y=f(L)y = f(L)y=f(L) .Example: b(I)=b(L)=1b(I) = b(L) = 1b(I)=b(L)=1 , so the number of bases is t(M;1,1)t(M; 1, 1)t(M;1,1) ; for U2,3U_{2,3}U2,3​ : t=x2+x+yt = x^2 + x + yt=x2+x+y gives 1+1+1=31 + 1 + 1 = 31+1+1=3 .

59. [Tutte–Grothendieck invariants] Brylawski's theorem: every T-G invariant fff satisfies f(M)=t(M;f(I),f(L))f(M) = t(M; f(I), f(L))f(M)=t(M;f(I),f(L)) , where ttt is the Tutte polynomial.The number of independent sets i(M)i(M)i(M) satisfies i(M)=i(M−e)+i(M/e)i(M) = i(M - e) + i(M/e)i(M)=i(M−e)+i(M/e) ( eee not a loop or isthmus), i(M)=2 i(M/e)i(M) = 2 \, i(M/e)i(M)=2i(M/e) ( eee an isthmus), i(M)=i(M−e)i(M) = i(M - e)i(M)=i(M−e) ( eee a loop). Which Tutte evaluation gives i(M)i(M)i(M) ?

    i(M)=t(M;2,1)\boldsymbol{i(M) = t(M; 2, 1)}i(M)=t(M;2,1) i(I)=2i(I) = 2i(I)=2 (the sets ∅\emptyset∅ and III ) and i(L)=1i(L) = 1i(L)=1 (only ∅\emptyset∅ ).Example: t(U2,3;2,1)=4+2+1=7t(U_{2,3}; 2, 1) = 4 + 2 + 1 = 7t(U2,3​;2,1)=4+2+1=7 : the empty set, 3 points, 3 pairs.

60. [Tutte–Grothendieck invariants] A Tutte–Grothendieck (T-G) invariant is a function fff from matroids to Z[x,y]\mathbb{Z}[x, y]Z[x,y] with: f(M1)=f(M2)f(M_1) = f(M_2)f(M1​)=f(M2​) for isomorphic M1≅M2M_1 \cong M_2M1​≅M2​ ; f(M)=f(M−e)+f(M/e)f(M) = f(M - e) + f(M/e)f(M)=f(M−e)+f(M/e) for eee neither a loop nor an isthmus; f(M)=f(I)⋅f(M/e)f(M) = f(I) \cdot f(M/e)f(M)=f(I)⋅f(M/e) for eee an isthmus ( III = the one-element isthmus matroid); f(M)=f(L)⋅f(M−e)f(M) = f(L) \cdot f(M - e)f(M)=f(L)⋅f(M−e)…

    Induction on ∣E∣|E|∣E∣ : apply the rule of fff for an element eee , induction to M−eM - eM−e and M/eM/eM/e , then the same rule of the Tutte polynomial. Base case ∣E∣=1|E| = 1∣E∣=1 : MMM is III or LLL .Case eee neither a loop nor an isthmus: f(M)=f(M−e)+f(M/e)=t(M−e;f(I),f(L))+t(M/e;f(I),f(L))=t(M;f(I),f(L))f(M) = f(M - e) + f(M/e) = t(M - e; f(I), f(L)) + t(M/e; f(I), f(L)) = t(M; f(I), f(L))f(M)=f(M−e)+f(M/e)=t(M−e;f(I),f(L))+t(M/e;f(I),f(L))=t(M;f(I),f(L)) .Case eee an isthmus: f(M)=f(I)⋅f(M…

61. [Tutte–Grothendieck invariants] A generalized T-G invariant fff is a matroid invariant with f(M)=f(I)⋅f(M/e)f(M) = f(I) \cdot f(M/e)f(M)=f(I)⋅f(M/e) for an isthmus eee , f(M)=f(L)⋅f(M−e)f(M) = f(L) \cdot f(M - e)f(M)=f(L)⋅f(M−e) for a loop eee , and f(M)=a⋅f(M−e)+b⋅f(M/e)f(M) = a \cdot f(M - e) + b \cdot f(M/e)f(M)=a⋅f(M−e)+b⋅f(M/e) for eee neither ( a,ba, ba,b fixed nonzero constants). How is f(M)f(M)f(M) obtained from the Tutte polynomial, for MMM on ground set EEE with rank function rrr ?

    f(M)=a∣E∣−r(E) br(E) t ⁣(M;f(I)b,f(L)a)\boldsymbol{f(M) = a^{|E| - r(E)} \, b^{r(E)} \; t\!\left(M; \tfrac{f(I)}{b}, \tfrac{f(L)}{a}\right)}f(M)=a∣E∣−r(E)br(E)t(M;bf(I)​,af(L)​) With a=b=1a = b = 1a=b=1 this is Brylawski's theorem f(M)=t(M;f(I),f(L))f(M) = t(M; f(I), f(L))f(M)=t(M;f(I),f(L)) .Example: f(M)=1f(M) = 1f(M)=1 for all MMM satisfies the rules with a=b=12a = b = \tfrac12a=b=21​ , and indeed 2−(∣E∣−r(E))2−r(E)t(M;2,2)=2−∣E∣⋅2∣E∣=12^{-(|E| - r(E))} 2^{-r(E)} t(M; 2, 2) = 2^{-|E|} \cdot…

62. [Tutte–Grothendieck invariants] What is an orientation of a graph GGG , and when is it acyclic?

    An assignment of a direction to every edge of GGG ; acyclic if it has no directed cycle. a(G)a(G)a(G) denotes the number of acyclic orientations of GGG .Example: a graph with mmm edges has 2m2^m2m orientations.

63. [Tutte–Grothendieck invariants] How many acyclic orientations does the triangle C3C_3C3​ have?

    6 Of the 23=82^3 = 823=8 orientations, exactly 2 are directed cycles (clockwise and counterclockwise). The triangle with edges a,b,ca, b, ca,b,c and its six acyclic orientations.

64. [Tutte–Grothendieck invariants] Theorem 9.21 (Stanley) Let a(G)a(G)a(G) be the number of acyclic orientations of a graph GGG , and M(G)M(G)M(G) its cycle matroid. Then a(G)= ?a(G) = \; ?a(G)=?

    a(G)=t(M(G);2,0)\boldsymbol{a(G) = t(M(G); 2, 0)}a(G)=t(M(G);2,0) a(G)a(G)a(G) is a T-G invariant with a(I)=2a(I) = 2a(I)=2 and a(L)=0a(L) = 0a(L)=0 .Example: M(C3)=U2,3M(C_3) = U_{2,3}M(C3​)=U2,3​ , t=x2+x+yt = x^2 + x + yt=x2+x+y , so a(C3)=4+2+0=6a(C_3) = 4 + 2 + 0 = 6a(C3​)=4+2+0=6 .

65. [Tutte–Grothendieck invariants] a(G)a(G)a(G) = number of acyclic orientations of a graph GGG . Why is a(G)=0⋅a(G−e)a(G) = 0 \cdot a(G - e)a(G)=0⋅a(G−e) when eee is a loop, and a(G)=2 a(G/e)a(G) = 2 \, a(G/e)a(G)=2a(G/e) when eee is an isthmus?

    A loop is a directed cycle in every orientation. An isthmus lies on no cycle, so each acyclic orientation of G/eG/eG/e extends to GGG with either direction of eee . So a(L)=0a(L) = 0a(L)=0 and a(I)=2a(I) = 2a(I)=2 , the values used in a(G)=t(M(G);2,0)a(G) = t(M(G); 2, 0)a(G)=t(M(G);2,0) .Example: the path with 2 edges (two isthmuses) has a=2⋅2=4a = 2 \cdot 2 = 4a=2⋅2=4 acyclic orientations, all 4 orientations.

66. [Tutte–Grothendieck invariants] The edge eee of a graph GGG joins uuu and vvv and is neither a loop nor an isthmus. Acyclic orientations of G−eG - eG−e are sorted by which directed paths exist in G−eG - eG−e : (1) none between uuu and vvv ; (2) u→vu \to vu→v only; (3) v→uv \to uv→u only; (4) both. Why are there none of kind (4)?

    A directed path u→vu \to vu→v followed by a directed path v→uv \to uv→u contains a directed cycle, so the orientation would not be acyclic. Hence a(G−e)=a1+a2+a3a(G - e) = a_1 + a_2 + a_3a(G−e)=a1​+a2​+a3​ , with aia_iai​ the number of acyclic orientations of G−eG - eG−e of kind (i)(i)(i) .Example: in C3C_3C3​ minus one edge (a path u,w,vu, w, vu,w,v ), the orientations u→w→vu \to w \to vu→w→v and v→w→uv \to w \to uv→w→u are of kinds (2) and (3), the other two of kind (1).

67. [Tutte–Grothendieck invariants] e=uve = uve=uv is neither a loop nor an isthmus of a graph GGG . a1,a2,a3a_1, a_2, a_3a1​,a2​,a3​ count the acyclic orientations of G−eG - eG−e with no directed path between uuu and vvv , with a directed path u→vu \to vu→v only, with a directed path v→uv \to uv→u only.Express a(G/e)a(G/e)a(G/e) and a(G)a(G)a(G) in terms of a1,a2,a3a_1, a_2, a_3a1​,a2​,a3​ .

    a(G/e)=a1\boldsymbol{a(G/e) = a_1}a(G/e)=a1​ and a(G)=2a1+a2+a3\boldsymbol{a(G) = 2a_1 + a_2 + a_3}a(G)=2a1​+a2​+a3​ , so a(G)=a(G−e)+a(G/e)a(G) = a(G - e) + a(G/e)a(G)=a(G−e)+a(G/e) . Kind 1: merging uuu and vvv creates no directed cycle, and eee may get either direction in GGG . Kinds 2 and 3: eee must point the same way as the existing path.Example: G=C3G = C_3G=C3​ , G−eG - eG−e a path with a1=2a_1 = 2a1​=2 , a2=a3=1a_2 = a_3 = 1a2​=a3​=1 : a(C3)=4+1+1=6a(C_3) = 4 + 1 + 1 = 6a(C3​)=4+1+1=6…

68. [Tutte–Grothendieck invariants] G1G_1G1​ and G2G_2G2​ are graphs with the same cycle matroid, M(G1)=M(G2)M(G_1) = M(G_2)M(G1​)=M(G2​) . What follows for their numbers of acyclic orientations?

    a(G1)=a(G2)a(G_1) = a(G_2)a(G1​)=a(G2​) a(G)=t(M(G);2,0)a(G) = t(M(G); 2, 0)a(G)=t(M(G);2,0) depends only on M(G)M(G)M(G) . So vertex gluing, vertex splitting and twisting (the operations relating graphs with the same cycle matroid) do not change a(G)a(G)a(G) .Example: a path with 2 edges and two disjoint edges have the same cycle matroid U2,2U_{2,2}U2,2​ , and a=4a = 4a=4 for both.

69. [Tutte–Grothendieck invariants] av(G)a_v(G)av​(G) = number of acyclic orientations of a graph GGG in which the vertex vvv is the unique source (every edge at vvv points away from vvv ). Which Tutte evaluation equals av(G)a_v(G)av​(G) ?

    av(G)=t(M(G);1,0)\boldsymbol{a_v(G) = t(M(G); 1, 0)}av​(G)=t(M(G);1,0) So av(G)a_v(G)av​(G) does not depend on which vertex vvv is chosen.Example: C3C_3C3​ : t(1,0)=1+1+0=2t(1, 0) = 1 + 1 + 0 = 2t(1,0)=1+1+0=2 ; with vvv the source, the edge opposite vvv can point either way.

70. [The chromatic polynomial] Which polynomial was Tutte's original motivation for his two-variable polynomial, and what did Tutte call the two-variable version?

    The chromatic polynomial of a graph; Tutte called his generalization the dichromatic polynomial. Crapo generalized Tutte's work to matroids, and Brylawski proved many of the foundational results for the matroid Tutte polynomial.

71. [The chromatic polynomial] What is a vertex coloring of a graph G=(V,E)G = (V, E)G=(V,E) , and when is it proper?

    A map c:V→Z+c : V \to \mathbb{Z}^+c:V→Z+ ; proper if c(u)≠c(v)c(u) \neq c(v)c(u)=c(v) whenever uuu and vvv are joined by an edge. Example: coloring the path u,w,vu, w, vu,w,v by c(u)=c(v)=1c(u) = c(v) = 1c(u)=c(v)=1 , c(w)=2c(w) = 2c(w)=2 is proper.

72. [The chromatic polynomial] What is the chromatic number of a graph GGG ?

    The smallest number of colors in a proper coloring of GGG . GGG has chromatic number 1 if and only if GGG has no edges.Example: the nnn -cycle CnC_nCn​ has chromatic number 2 if nnn is even and 3 if nnn is odd.

73. [The chromatic polynomial] Which graphs have chromatic number at most 2, and why?

    Exactly the bipartite graphs. Color one side of a bipartition red and the other blue; conversely, the red vertices and the blue vertices of a proper 2-coloring form the two sides.Example: C4C_4C4​ is bipartite and 2-colorable, C3C_3C3​ is neither.

74. [The chromatic polynomial] What is the chromatic polynomial χG(λ)\chi_G(\lambda)χG​(λ) of a graph GGG ( λ\lambdaλ a non-negative integer)?

    The number of proper colorings of GGG using at most λ\lambdaλ colors. So χG(λ)>0\chi_G(\lambda) > 0χG​(λ)>0 if and only if GGG has chromatic number at most λ\lambdaλ .Example: one edge K2K_2K2​ : χK2(λ)=λ(λ−1)\chi_{K_2}(\lambda) = \lambda(\lambda - 1)χK2​​(λ)=λ(λ−1) , so χK2(2)=2\chi_{K_2}(2) = 2χK2​​(2)=2 .

75. [The chromatic polynomial] The chromatic polynomial χG(λ)\chi_G(\lambda)χG​(λ) of a graph GGG is the number of proper colorings of the vertices of GGG with at most λ\lambdaλ colors (adjacent vertices get different colors). Compute χG1(λ)\chi_{G_1}(\lambda)χG1​​(λ) for the complete graph G1=K4G_1 = K_4G1​=K4​ . How many proper colorings use at most 4 colors, and at most 3?

    χK4(λ)=λ(λ−1)(λ−2)(λ−3)\boldsymbol{\chi_{K_4}(\lambda) = \lambda(\lambda - 1)(\lambda - 2)(\lambda - 3)}χK4​​(λ)=λ(λ−1)(λ−2)(λ−3) ; 24 with 4 colors, 0 with 3. Color vertices 1, 2, 3, 4 in order: each vertex must avoid the colors of all earlier ones, giving λ,λ−1,λ−2,λ−3\lambda, \lambda - 1, \lambda - 2, \lambda - 3λ,λ−1,λ−2,λ−3 choices.Example: χK4(4)=4⋅3⋅2⋅1=24\chi_{K_4}(4) = 4 \cdot 3 \cdot 2 \cdot 1 = 24χK4​​(4)=4⋅3⋅2⋅1=24 , χK4(3)=3⋅2⋅1⋅0=0\chi_{K_4}(3) = 3 \cdot 2 \cdot 1 \cdot 0 = 0χK4​​…

76. [The chromatic polynomial] The chromatic polynomial χG(λ)\chi_G(\lambda)χG​(λ) of a graph GGG is the number of proper colorings of the vertices of GGG with at most λ\lambdaλ colors (adjacent vertices get different colors).What is χT(λ)\chi_T(\lambda)χT​(λ) for a tree TTT with nnn vertices, and why?

    χT(λ)=λ(λ−1)n−1\boldsymbol{\chi_T(\lambda) = \lambda(\lambda - 1)^{n - 1}}χT​(λ)=λ(λ−1)n−1 Order the vertices so that each one after the first is adjacent to exactly one earlier vertex: λ\lambdaλ choices for the first, λ−1\lambda - 1λ−1 for each other.Since χT(2)=2>0\chi_T(2) = 2 > 0χT​(2)=2>0 , every tree is bipartite. Example: the tree G2G_2G2​ (6 vertices), colored in the order 1, 3, 2, 4, 5, 6: χG2(λ)=λ(λ−1)5\chi_{G_2}(\lambda) = \lambda(\lambda - 1)^5χG2​​(λ)=λ(λ−1)5 .

77. [The chromatic polynomial] The chromatic polynomial χG(λ)\chi_G(\lambda)χG​(λ) of a graph GGG is the number of proper colorings of the vertices of GGG with at most λ\lambdaλ colors (adjacent vertices get different colors). G3G_3G3​ is a triangle on the vertices 1, 2, 3 with one more vertex 4 adjacent only to vertex 3. What is χG3(λ)\chi_{G_3}(\lambda)χG3​​(λ) ?

    χG3(λ)=λ(λ−1)2(λ−2)\boldsymbol{\chi_{G_3}(\lambda) = \lambda(\lambda - 1)^2(\lambda - 2)}χG3​​(λ)=λ(λ−1)2(λ−2) λ(λ−1)(λ−2)\lambda(\lambda - 1)(\lambda - 2)λ(λ−1)(λ−2) colorings of the triangle, then λ−1\lambda - 1λ−1 colors for vertex 4. G3G_3G3​ is the graph on the right.

78. [The chromatic polynomial] The chromatic polynomial χG(λ)\chi_G(\lambda)χG​(λ) of a graph GGG is the number of proper colorings of the vertices of GGG with at most λ\lambdaλ colors (adjacent vertices get different colors). Compute χG(λ)\chi_G(\lambda)χG​(λ) for this graph GGG (the 4-cycle 1, 2, 3, 4 with the diagonal 13).

    χG(λ)=λ(λ−1)(λ−2)2\boldsymbol{\chi_G(\lambda) = \lambda(\lambda - 1)(\lambda - 2)^2}χG​(λ)=λ(λ−1)(λ−2)2 Color vertices 1, 2, 3 in λ(λ−1)(λ−2)\lambda(\lambda - 1)(\lambda - 2)λ(λ−1)(λ−2) ways. Vertex 4 (adjacent to 1 and 3): if it gets the color of vertex 2, 1 choice; otherwise λ−3\lambda - 3λ−3 choices. λ(λ−1)(λ−2)(1+(λ−3))=λ(λ−1)(λ−2)2\lambda(\lambda - 1)(\lambda - 2)\bigl(1 + (\lambda - 3)\bigr) = \lambda(\lambda - 1)(\lambda - 2)^2λ(λ−1)(λ−2)(1+(λ−3))=λ(λ−1)(λ−2)2

79. [The chromatic polynomial] Proposition 9.26 Let GGG be a simple graph and eee an edge. Then χG(λ)= ?\chi_G(\lambda) = \; ?χG​(λ)=? (deletion–contraction for the chromatic polynomial)

    χG(λ)=χG−e(λ)−χG/e(λ)\boldsymbol{\chi_G(\lambda) = \chi_{G - e}(\lambda) - \chi_{G/e}(\lambda)}χG​(λ)=χG−e​(λ)−χG/e​(λ) A minus sign, unlike the Tutte polynomial recursion.Example: G=K2G = K_2G=K2​ : χK2=χ2K1−χK1=λ2−λ\chi_{K_2} = \chi_{2K_1} - \chi_{K_1} = \lambda^2 - \lambdaχK2​​=χ2K1​​−χK1​​=λ2−λ .

80. [The chromatic polynomial] eee is an edge with ends u,vu, vu,v in a simple graph GGG . Why is χG−e(λ)=χG(λ)+χG/e(λ)\chi_{G - e}(\lambda) = \chi_G(\lambda) + \chi_{G/e}(\lambda)χG−e​(λ)=χG​(λ)+χG/e​(λ) ?

    Split the proper colorings of G−eG - eG−e : those with c(u)≠c(v)c(u) \neq c(v)c(u)=c(v) are exactly the proper colorings of GGG ; those with c(u)=c(v)c(u) = c(v)c(u)=c(v) correspond exactly to the proper colorings of G/eG/eG/e . Example: G=K2G = K_2G=K2​ : G−eG - eG−e has λ2\lambda^2λ2 colorings, λ(λ−1)\lambda(\lambda - 1)λ(λ−1) with different colors and λ=χK1(λ)\lambda = \chi_{K_1}(\lambda)λ=χK1​​(λ) with equal colors.

81. [The chromatic polynomial] χG(λ)=χG−e(λ)−χG/e(λ)\chi_G(\lambda) = \chi_{G - e}(\lambda) - \chi_{G/e}(\lambda)χG​(λ)=χG−e​(λ)−χG/e​(λ) . Parallel edges do not change the chromatic polynomial. Recompute χG(λ)\chi_G(\lambda)χG​(λ) for this graph with eee the edge 12. What are G−eG - eG−e and G/eG/eG/e ?

    G−eG - eG−e is a triangle with a pendant vertex, G/eG/eG/e is a triangle with one doubled edge; χG=λ(λ−1)2(λ−2)−λ(λ−1)(λ−2)=λ(λ−1)(λ−2)2\chi_G = \lambda(\lambda - 1)^2(\lambda - 2) - \lambda(\lambda - 1)(\lambda - 2) = \lambda(\lambda - 1)(\lambda - 2)^2χG​=λ(λ−1)2(λ−2)−λ(λ−1)(λ−2)=λ(λ−1)(λ−2)2 . Triangle 1, 3, 4 with vertex 2 attached to 3: λ(λ−1)2(λ−2)\lambda(\lambda - 1)^2(\lambda - 2)λ(λ−1)2(λ−2) . Merging 1 and 2 gives a triangle (edges from 13 and 23 parallel): λ(λ−1)(λ−2)\lambda(\lambda…

82. [The chromatic polynomial] Why is the number of proper colorings χG(λ)\chi_G(\lambda)χG​(λ) of a graph GGG with at most λ\lambdaλ colors always a polynomial in λ\lambdaλ ?

    Induction on the number of edges with χG=χG−e−χG/e\chi_G = \chi_{G - e} - \chi_{G/e}χG​=χG−e​−χG/e​ ; graphs where the recursion does not apply are easy to compute directly. Example: the edgeless graph on nnn vertices has χ=λn\chi = \lambda^nχ=λn ; a graph with a loop has χ=0\chi = 0χ=0 .

83. [The chromatic polynomial] Why does any formula relating the Tutte polynomial t(M(G))t(M(G))t(M(G)) to the chromatic polynomial χG(λ)\chi_G(\lambda)χG​(λ) need a correction factor?

    M(G)M(G)M(G) is defined on the edges of GGG , but χG\chi_GχG​ depends on the vertices. Example: K2K_2K2​ and K2K_2K2​ plus an isolated vertex have the same cycle matroid U1,1U_{1,1}U1,1​ , but χ=λ(λ−1)\chi = \lambda(\lambda - 1)χ=λ(λ−1) and λ2(λ−1)\lambda^2(\lambda - 1)λ2(λ−1) .

84. [The chromatic polynomial] Theorem 9.28 Let GGG be a connected graph with vertex set VVV and cycle matroid M(G)M(G)M(G) . Then χG(λ)= ?\chi_G(\lambda) = \; ?χG​(λ)=? (in terms of the Tutte polynomial)

    χG(λ)=(−1)∣V∣−1λ⋅t(M(G);1−λ,0)\boldsymbol{\chi_G(\lambda) = (-1)^{|V| - 1} \lambda \cdot t(M(G); 1 - \lambda, 0)}χG​(λ)=(−1)∣V∣−1λ⋅t(M(G);1−λ,0) Example: C3C_3C3​ , t=x2+x+yt = x^2 + x + yt=x2+x+y : (−1)2λ((1−λ)2+(1−λ))=λ(λ−1)(λ−2)(-1)^2 \lambda\bigl((1 - \lambda)^2 + (1 - \lambda)\bigr) = \lambda(\lambda - 1)(\lambda - 2)(−1)2λ((1−λ)2+(1−λ))=λ(λ−1)(λ−2) .

85. [The chromatic polynomial] The chromatic polynomial χG(λ)\chi_G(\lambda)χG​(λ) of a graph GGG is the number of proper colorings of the vertices of GGG with at most λ\lambdaλ colors (adjacent vertices get different colors).What are χI(λ)\chi_I(\lambda)χI​(λ) and χL(λ)\chi_L(\lambda)χL​(λ) for the single-edge graphs III (an isthmus) and LLL (a loop), and what is χG\chi_GχG​ for a graph GGG with a loop eee ?

    χI(λ)=λ(λ−1)\boldsymbol{\chi_I(\lambda) = \lambda(\lambda - 1)}χI​(λ)=λ(λ−1) , χL(λ)=0\boldsymbol{\chi_L(\lambda) = 0}χL​(λ)=0 , and χG=0\chi_G = 0χG​=0 . A loop joins a vertex to itself, so no coloring is proper. So χG(λ)=χL(λ)⋅χG−e(λ)\chi_G(\lambda) = \chi_L(\lambda) \cdot \chi_{G - e}(\lambda)χG​(λ)=χL​(λ)⋅χG−e​(λ) holds for a loop eee .

86. [The chromatic polynomial] The chromatic polynomial χG(λ)\chi_G(\lambda)χG​(λ) of a graph GGG is the number of proper colorings of the vertices of GGG with at most λ\lambdaλ colors (adjacent vertices get different colors). e=uve = uve=uv is an isthmus of GGG , and Gu,GvG_u, G_vGu​,Gv​ are the components of G−eG - eG−e containing uuu and vvv . Why is χG/e(λ)=χGu(λ) χGv(λ)λ\chi_{G/e}(\lambda) = \frac{\chi_{G_u}(\lambda) \, \chi_{G_v}(\lambda)}{\lambda}χG/e​(λ)=λχGu​​(λ)χGv​​(λ)​ ?

    The proper colorings of G−eG - eG−e with c(u)=c(v)c(u) = c(v)c(u)=c(v) are the proper colorings of G/eG/eG/e , and they are 1λ\frac{1}{\lambda}λ1​ of all χGuχGv\chi_{G_u}\chi_{G_v}χGu​​χGv​​ colorings of G−eG - eG−e . For a fixed coloring of GuG_uGu​ , the colorings of GvG_vGv​ fall into λ\lambdaλ classes of equal size χGv(λ)/λ\chi_{G_v}(\lambda)/\lambdaχGv​​(λ)/λ by the color of vvv ; exactly one class matches the color of uuu . Example: G=K2G = K_2G=K2​ , Gu=Gv=K1G_u = G_v = K_1Gu​=Gv​=K1​ :…

87. [The chromatic polynomial] For an isthmus e=uve = uve=uv of GGG : χG−e=χGuχGv\chi_{G - e} = \chi_{G_u}\chi_{G_v}χG−e​=χGu​​χGv​​ and χG/e=χGuχGv/λ\chi_{G/e} = \chi_{G_u}\chi_{G_v}/\lambdaχG/e​=χGu​​χGv​​/λ ( Gu,GvG_u, G_vGu​,Gv​ the components of G−eG - eG−e ). Also χG=χG−e−χG/e\chi_G = \chi_{G - e} - \chi_{G/e}χG​=χG−e​−χG/e​ .How is χG(λ)\chi_G(\lambda)χG​(λ) related to χG/e(λ)\chi_{G/e}(\lambda)χG/e​(λ) when eee is an isthmus?

    χG(λ)=(λ−1) χG/e(λ)\boldsymbol{\chi_G(\lambda) = (\lambda - 1) \, \chi_{G/e}(\lambda)}χG​(λ)=(λ−1)χG/e​(λ) χG=χG−e−χG/e=λχG/e−χG/e\chi_G = \chi_{G - e} - \chi_{G/e} = \lambda \chi_{G/e} - \chi_{G/e}χG​=χG−e​−χG/e​=λχG/e​−χG/e​ .Example: a path with 2 edges has χ=λ(λ−1)2=(λ−1)⋅λ(λ−1)\chi = \lambda(\lambda - 1)^2 = (\lambda - 1) \cdot \lambda(\lambda - 1)χ=λ(λ−1)2=(λ−1)⋅λ(λ−1) , and contracting one edge leaves K2K_2K2​ .

88. [The chromatic polynomial] Theorem: for a connected graph G=(V,E)G = (V, E)G=(V,E) , χG(λ)=(−1)∣V∣−1λ⋅t(M(G);1−λ,0)\chi_G(\lambda) = (-1)^{|V| - 1} \lambda \cdot t(M(G); 1 - \lambda, 0)χG​(λ)=(−1)∣V∣−1λ⋅t(M(G);1−λ,0) .Which Tutte–Grothendieck invariant does the proof use, and what are its values on an isthmus III and a loop LLL ?

    fG(λ)=(−1)∣V∣−1χG(λ)/λ\boldsymbol{f_G(\lambda) = (-1)^{|V| - 1} \chi_G(\lambda) / \lambda}fG​(λ)=(−1)∣V∣−1χG​(λ)/λ , with fI=1−λf_I = 1 - \lambdafI​=1−λ and fL=0f_L = 0fL​=0 . So Brylawski's theorem gives fG(λ)=t(M(G);1−λ,0)f_G(\lambda) = t(M(G); 1 - \lambda, 0)fG​(λ)=t(M(G);1−λ,0) .Example: fI=(−1)1λ(λ−1)/λ=1−λf_I = (-1)^1 \lambda(\lambda - 1)/\lambda = 1 - \lambdafI​=(−1)1λ(λ−1)/λ=1−λ .

89. [The chromatic polynomial] fG(λ)=(−1)∣V∣−1χG(λ)/λf_G(\lambda) = (-1)^{|V| - 1} \chi_G(\lambda)/\lambdafG​(λ)=(−1)∣V∣−1χG​(λ)/λ , and χG=χG−e−χG/e\chi_G = \chi_{G - e} - \chi_{G/e}χG​=χG−e​−χG/e​ for eee not a loop.Why does fG=fG−e+fG/ef_G = f_{G - e} + f_{G/e}fG​=fG−e​+fG/e​ hold with a plus sign, for eee neither a loop nor an isthmus?

    G/eG/eG/e has one vertex fewer than GGG , so its sign (−1)∣V∣−2(-1)^{|V| - 2}(−1)∣V∣−2 is opposite and turns −χG/e-\chi_{G/e}−χG/e​ into +fG/e+f_{G/e}+fG/e​ . G−eG - eG−e has the same ∣V∣|V|∣V∣ , so (−1)∣V∣−1χG−e/λ=fG−e(-1)^{|V| - 1}\chi_{G - e}/\lambda = f_{G - e}(−1)∣V∣−1χG−e​/λ=fG−e​ . For an isthmus, χG=(λ−1)χG/e\chi_G = (\lambda - 1)\chi_{G/e}χG​=(λ−1)χG/e​ gives fG=(1−λ)fG/ef_G = (1 - \lambda) f_{G/e}fG​=(1−λ)fG/e​ .

90. [The chromatic polynomial] Why doesn't the chromatic polynomial χG(λ)\chi_G(\lambda)χG​(λ) itself, or gG(λ)=(−1)∣V∣−1χG(λ)g_G(\lambda) = (-1)^{|V| - 1}\chi_G(\lambda)gG​(λ)=(−1)∣V∣−1χG​(λ) , work as a Tutte–Grothendieck invariant?

    χG=χG−e−χG/e\chi_G = \chi_{G - e} - \chi_{G/e}χG​=χG−e​−χG/e​ has a minus sign; ggg fixes the sign but fails the isthmus rule. gI(λ)=−λ(λ−1)g_I(\lambda) = -\lambda(\lambda - 1)gI​(λ)=−λ(λ−1) , but gG=(1−λ)gG/eg_G = (1 - \lambda) g_{G/e}gG​=(1−λ)gG/e​ for an isthmus, not gI⋅gG/eg_I \cdot g_{G/e}gI​⋅gG/e​ . Dividing by λ\lambdaλ fixes it.Moral: an induction proof needs the right statement before it starts.

91. [The chromatic polynomial] G=(V,E)G = (V, E)G=(V,E) is a graph with κ(G)\kappa(G)κ(G) connected components. How is χG(λ)\chi_G(\lambda)χG​(λ) obtained from the Tutte polynomial?

    χG(λ)=λκ(G)(−1)∣V∣−κ(G) t(M(G);1−λ,0)\boldsymbol{\chi_G(\lambda) = \lambda^{\kappa(G)} (-1)^{|V| - \kappa(G)} \, t(M(G); 1 - \lambda, 0)}χG​(λ)=λκ(G)(−1)∣V∣−κ(G)t(M(G);1−λ,0) With κ(G)=1\kappa(G) = 1κ(G)=1 this is (−1)∣V∣−1λ t(M(G);1−λ,0)(-1)^{|V| - 1}\lambda \, t(M(G); 1 - \lambda, 0)(−1)∣V∣−1λt(M(G);1−λ,0) .Example: K2K_2K2​ plus an isolated vertex: κ=2\kappa = 2κ=2 , ∣V∣=3|V| = 3∣V∣=3 , t=xt = xt=x : λ2⋅(−1)⋅(1−λ)=λ2(λ−1)\lambda^2 \cdot (-1) \cdot (1 - \lambda) = \lambda^2(\lambda - 1)λ2⋅(−1…

92. [The chromatic polynomial] What is the characteristic polynomial p(M;λ)p(M; \lambda)p(M;λ) of a matroid MMM on ground set EEE (with rank function rrr )?

    p(M;λ)=(−1)r(E) t(M;1−λ,0)\boldsymbol{p(M; \lambda) = (-1)^{r(E)} \, t(M; 1 - \lambda, 0)}p(M;λ)=(−1)r(E)t(M;1−λ,0) Defined for every matroid, graphic or not. For a connected graph GGG , r(E)=∣V∣−1r(E) = |V| - 1r(E)=∣V∣−1 , so χG(λ)=λ p(M(G);λ)\chi_G(\lambda) = \lambda \, p(M(G); \lambda)χG​(λ)=λp(M(G);λ) .Example: p(U2,3;λ)=(1−λ)2+(1−λ)=(λ−1)(λ−2)p(U_{2,3}; \lambda) = (1 - \lambda)^2 + (1 - \lambda) = (\lambda - 1)(\lambda - 2)p(U2,3​;λ)=(1−λ)2+(1−λ)=(λ−1)(λ−2) .

93. [The chromatic polynomial] Proposition 9.30 Let MMM be a matroid on the ground set EEE with rank function rrr . Then the characteristic polynomial p(M;λ)=(−1)r(E)t(M;1−λ,0)p(M; \lambda) = (-1)^{r(E)} t(M; 1 - \lambda, 0)p(M;λ)=(−1)r(E)t(M;1−λ,0) equals which sum over subsets?

    p(M;λ)=∑A⊆E(−1)∣A∣λr(E)−r(A)\boldsymbol{p(M; \lambda) = \displaystyle\sum_{A \subseteq E} (-1)^{|A|} \lambda^{r(E) - r(A)}}p(M;λ)=A⊆E∑​(−1)∣A∣λr(E)−r(A) From t(M;x,y)=∑A(x−1)r(E)−r(A)(y−1)∣A∣−r(A)t(M; x, y) = \sum_{A} (x - 1)^{r(E) - r(A)} (y - 1)^{|A| - r(A)}t(M;x,y)=∑A​(x−1)r(E)−r(A)(y−1)∣A∣−r(A) at x=1−λx = 1 - \lambdax=1−λ , y=0y = 0y=0 .Example: U2,3U_{2,3}U2,3​ : λ2−3λ+3−1=λ2−3λ+2\lambda^2 - 3\lambda + 3 - 1 = \lambda^2 - 3\lambda + 2λ2−3λ+3−1=λ2−3λ+2 (from A=∅A = \emptysetA=∅ , the 3 poi…

94. [The chromatic polynomial] t(M∗;x,y)=t(M;y,x)t(M^*; x, y) = t(M; y, x)t(M∗;x,y)=t(M;y,x) , and for a connected planar graph GGG with planar dual G∗G^*G∗ , M(G)∗=M(G∗)M(G)^* = M(G^*)M(G)∗=M(G∗) .For a connected planar graph GGG , what does t(M(G);0,1−λ)t(M(G); 0, 1 - \lambda)t(M(G);0,1−λ) give?

    The chromatic polynomial of the dual graph G∗G^*G∗ : χG∗(λ)=(−1)∣V(G∗)∣−1λ t(M(G);0,1−λ)\chi_{G^*}(\lambda) = (-1)^{|V(G^*)| - 1}\lambda \, t(M(G); 0, 1 - \lambda)χG∗​(λ)=(−1)∣V(G∗)∣−1λt(M(G);0,1−λ) . Because t(M(G);0,1−λ)=t(M(G∗);1−λ,0)t(M(G); 0, 1 - \lambda) = t(M(G^*); 1 - \lambda, 0)t(M(G);0,1−λ)=t(M(G∗);1−λ,0) . A second interpretation, valid for all graphs, counts nowhere-zero flows.Example: G=C3G = C_3G=C3​ , t=x2+x+yt = x^2 + x + yt=x2+x+y , t(0,1−λ)=1−λt(0, 1 - \lambda) = 1 - \lambdat(…

95. [The chromatic polynomial] GGG is a graph whose edges are oriented, and HHH is a finite abelian group (written additively). What is an HHH -flow, and when is it nowhere-zero?

    Weights w(e)∈Hw(e) \in Hw(e)∈H on the edges with, at every vertex, (sum of weights in) = (sum of weights out); nowhere-zero if all w(e)≠0w(e) \neq 0w(e)=0 . The condition at each vertex is Kirchhoff's current law. Example: a nowhere-zero Z4\mathbb{Z}_4Z4​ -flow.

96. [The chromatic polynomial] The edges carry weights in Z4\mathbb{Z}_4Z4​ . Check Kirchhoff's law at the vertices www and vvv .

    At www : in 222 , out 3+3=6≡23 + 3 = 6 \equiv 23+3=6≡2 . At vvv : in 3+1=4≡03 + 1 = 4 \equiv 03+1=4≡0 , out nothing ( 000 ). At xxx : in 3, out 3. At uuu : in 3, out 2+1=32 + 1 = 32+1=3 . So this is a nowhere-zero Z4\mathbb{Z}_4Z4​ -flow.

97. [The chromatic polynomial] Proposition 9.31 (first surprise) For a graph GGG and a finite abelian group HHH , how does the number of nowhere-zero HHH -flows depend on the orientation of GGG ?

    It does not depend on the orientation. Reversing an edge eee and replacing w(e)w(e)w(e) by −w(e)-w(e)−w(e) is a bijection between nowhere-zero flows of the two orientations. Example: in Z4\mathbb{Z}_4Z4​ , reversing the edge wxwxwx changes its weight from 3 to −3=1-3 = 1−3=1 .

98. [The chromatic polynomial] Theorem 9.32 (second surprise) On what does the number of nowhere-zero HHH -flows of a graph GGG depend, as HHH ranges over finite abelian groups?

    Only on ∣H∣|H|∣H∣ , the number of elements of HHH . So any abelian group of order kkk may be replaced by Zk\mathbb{Z}_kZk​ .Example: Z4\mathbb{Z}_4Z4​ and Z2×Z2\mathbb{Z}_2 \times \mathbb{Z}_2Z2​×Z2​ give the same number of nowhere-zero flows.

99. [The chromatic polynomial] What is the flow polynomial χG∗(k)\chi^*_G(k)χG∗​(k) of a graph GGG ?

    The number of nowhere-zero HHH -flows on GGG for an abelian group HHH with ∣H∣=k|H| = k∣H∣=k . Well defined because the number depends neither on the orientation nor on the structure of HHH .Example: the cycle CnC_nCn​ (oriented cyclically) carries the same weight on every edge, so χCn∗(k)=k−1\chi^*_{C_n}(k) = k - 1χCn​∗​(k)=k−1 .

100. [The chromatic polynomial] Theorem 9.33 (third surprise) Let G=(V,E)G = (V, E)G=(V,E) be a connected graph. The flow polynomial χG∗(k)\chi^*_G(k)χG∗​(k) (number of nowhere-zero flows with values in an abelian group of order kkk ) equals … ?

     χG∗(k)=(−1)∣V∣+∣E∣+1 t(M(G);0,1−k)\boldsymbol{\chi^*_G(k) = (-1)^{|V| + |E| + 1} \, t(M(G); 0, 1 - k)}χG∗​(k)=(−1)∣V∣+∣E∣+1t(M(G);0,1−k) The group enters only through y=1−ky = 1 - ky=1−k , which proves that only ∣H∣|H|∣H∣ matters. The proof is the same as for the chromatic polynomial, with a T-G invariant.Example: C3C_3C3​ : (−1)7t(0,1−k)=−(1−k)=k−1(-1)^7 t(0, 1 - k) = -(1 - k) = k - 1(−1)7t(0,1−k)=−(1−k)=k−1 .