Graphs and Combinatorial Invariants

(Ideas of W.T. Tutte)

This course is an introduction to some advanced aspects of graph theory and to Tutte invariants of graphs and matroids. We will study initially portions of the book

- W.T. Tutte,
- Graph Theory,
- Cambridge University Press.

- James Oxley,
- Matroid Theory,
- Oxford University Press,

- Neil White, editor,
- Combinatorial Geometries, Ch. 7, and
- Matroid Applications, Ch. 6,
- Cambridge University Press.

The focus of the course is on some contributions of Tutte, arguably the greatest graph theorist of the last century (neglecting Robertson and Seymour as transcenturial), and work that follows in his spirit. Some light reading about Prof. Tutte:

- A short biography from Tutte's home university.
- The New York Times obituary.
- The appreciation in the Notices of the American Mathematical Society (March, 2004).

The course is not normally suitable for first-year graduate students. However, the only specific prerequisites are the traditional "mathematical maturity" and familiarity with groups, rings, and fields; and basic graduate algebra is very helpful.

PLACE: LN-2205

TIME: Mon., Wed., Fri. 2:20-3:20.

Friday, April 23, 3:30-4:30 p.m. in LN-2205.

Thursday, April 29, 4:30-5:30 in LN-2205.

Thursday, May 6, 1:15-2:30 in LN-2205.

Finals week: Wednesday, May 12, 1:00-2:30 in LN-2205.

My regular office hours, which are mainly for the undergraduates, are

I will be happy to see you at these or other times as far as possible. If necessary we can make appointments.

All students are encouraged to attend the Combinatorics Seminar, time to be announced. There will be talks you can't understand, as well as some you can't help understanding, on all kinds of topics in graph theory and other combinatorics as well as in number theory (and sometimes both at once). (You'll be surprised how much you learn by not understanding a great many talks.)

I will lecture, for the most part.

Student work: You will have to work hard sometimes to understand the lectures and readings. Keep your colored pencils handy. Your grade will be based on handed-in problems and (possibly) presentations. I will also meet with each of you individually on a semiregular basis.

I expect you to **try all the exercises** at the end of the chapters and the additional exercises (below). You don't have to solve all of them! I will collect your written solutions to some or all of the following assignments, some from Tutte and some from the additional problems. The list of hand-in problems is not compulsory but you should turn in as many as you can. You may submit second solutions of any problems to raise your grade.

**Rules for write-ups that you hand in:**
Submit each different problem on a separate piece of paper. If you need more than one paper, staple them together. (Thank you. This will greatly assist both of us in the homework procedures.)

The last dates for accepting homework from each part of the course. There will be *no exceptions* barring medical or other disaster.

Ch. I: Friday, March 26.

Ch. II: Friday, April 2.

Ch. III: Wednesday, April 14.

Ch. VII: Friday, April 23 (5:30 p.m.).

Ch. IX: First tries: Wednesday, May 5 (5:30 p.m.). If you turn in a solution later, and I manage to return it before the final deadline, you may turn in a second version. Final versions: Thursday, May 13 (5:00 p.m.).

One reason for having deadlines is that you will have presentations to do in class toward the end of the term, and you won't be able to handle your work if you let it pile up. Another reason is that most of you have not been handing in the homework. A third reason is that I can only grade so much at once, and I have to be done before the grades are due.

The syllabus is tentative and partial. It will get filled out and corrected as the course progresses.

#### Chapter I: Graphs and Subgraphs.

- Description: Basics.
*Problems.*Hand in ## 1 - 7.- In a graph G, for vertices v, w, define v ~ w if v = w or there exists an arc in G whose endpoints are v and w. (a) Prove:
**Lemma A.**~ is an equivalence relation. Let V_{1}, ..., V_{k}be the equivalence classes. (b) Prove:**Theorem B.**The components of G are precisely the subgraphs G[V_{i}]. - Prove the following characterization of isthmi.
**Theorem I.31a**: An edge is an isthmus if and only if it lies in no circuit of G. (This is much stronger than Theorem I.31.) - Prove that, if e is an isthmus of G and f is an isthmus of G - e, then f is an isthmus of G.
- Prove that, if F is a maximal forest of G and e is any edge of G not in F, then e is not an isthmus in G.
- For a set S, let P
_{k}(S) denote the class of all k-element subsets of S. Define P to be the simple graph whose vertex set is P_{2}({1,2,...,5}) and in which vertices {i,j} and {k,l} are adjacent if and only if {i,j} and {k,l} are disjoint sets. (Note that V(P) can be thought of as E(K_{5}.)- Show that P is the Petersen graph (see Fig. IV.2.8, right).
- Show that P has exactly 120 automorphisms.
- Show that, in P, every 3-arc is equivalent to every other, in the sense that there is an automorphism of P that carries the first into the second.
- Is the same true of 4-arcs?

- In a graph G, for vertices v, w, define v ~ w if v = w or there exists an arc in G whose endpoints are v and w. (a) Prove:

#### Chapter II: Contractions and the Theorem of Menger.

- Description: More basics; and famous theorems.
*Problems.*Hand in ## 2, 3 (optional), 4, 6, 7.- Prove König's theorem directly from Menger's theorem (Theorem II.35).
**König's Theorem.**Let G be a bipartite graph with bipartition (U, V). The largest size of a matching (i.e., partial 1-factor) equals the smallest size of a vertex cover (a set X of vertices such that every edge has at least one endpoint in X). - The usual form of Menger's Theorem is not Tutte's Theorem II.35. Define an xy-
*separating set*to be a vertex set X such that x and y are not joined by a path in G - X. Use results in Ch. II to prove the usual Menger's Theorem, which is**Theorem M**: Let x, y be nonadjacent vertices in a graph G. The smallest size of an xy-separating set equals the largest number of internally disjoint xy-paths.

- Prove König's theorem directly from Menger's theorem (Theorem II.35).

#### Chapter III: 2-Connection.

- Description: Basic structure theory.
*Problems.*Hand in ## 1 - 4.- Prove the following `vertex' version of Theorem III.7.
**Theorem III.7v.**Let G be an inseparable graph and let U, V be nonnull vertex sets in G. Then mu_{G}(U,V) >= 2 with these exceptions: when U = V and |U| = 1, or when G = K_{2}(or just possibly one or two other exceptional cases that I missed).

- Prove the following `vertex' version of Theorem III.7.

#### Chapter VII: Alternating Paths.

- Description: Existence theory of perfect matchings and of subgraphs with prescribed degrees.
- Background reading for digraphs: The beginnings of Sections VI.1 and VI.2.
*Problems.*Hand in ## 1, 2, 4 - 9, 12, 13.- Make it interesting! Do it so there exist edges of all three types, insofar as you can.

- The situation is that of Section VII.2. Given K, P, and e as defined therein, let Q be a path belonging to J
_{K}(e). Prove that PQ is in J(r). - At some point in Tutte's algorithm for improving an f-limited subgraph F (pp. 174-5), we may be blocked from further improvement at r because
- every other deficient (unfilled) vertex is inaccessible by J(r)-paths and
- delta(r) = 1 or r is unicursal.

**Question:**Is it impossible to improve F by changing to some other center r' and applying Tutte's algorithm from r' ? - Take G = the Petersen graph with a function f : V(G) —>
**Z**. Pick a starting f-limited subgraph F that is not an f-factor, and apply*Tutte's algorithm*(not any other method) to improve it to find either an F-factor or an f-barrier.- f equals 1 for all but two vertices, at which it equals 2. (There are 2 such functions up to isomorphism. Pick one.)
- f equals 1 for all vertices but two nonadjacent ones, at which it equals 3.

- Deduce Theorem VII.26 from VII.25 by duality of pairs B = (S,T) and B' = (T,S), instead of by a direct calculation as in the book.
- (I got this from Pearls in Graph Theory by Hartsfield and Ringel.) Deduce the following amusing corollary of Petersen's theorem: Any simple cubic graph that has no isthmus can be decomposed into subgraphs isomorphic to P
_{3}, the arc of length 3. ("Decomposing" a graph means partitioning the edges. You may repeat vertices as much as is convenient.) The best part of this is:**Lemma**. A simple cubic graph has a decomposition into subgraphs isomorphic to P_{3}if and only if it has a 1-factor. - Does Petersen's Theorem characterize the simple cubic graphs that have a 1-factor?
- Deduce Theorems 24 and 32 from Theorem 32M.
**Theorem 32M**. min { delta(F) : F is an f-limited spanning subgraph} = max { delta(B) : B = (S,T) where S and T are disjoint subsets of V(G) }. - Prove Theorem VII.33.
- Write out a complete proof of Hall's Theorem (II.39) from Theorem VII.35.
- Write out the full proof of Theorem VII.35 (the Bipartite f-Factor Theorem) as outlined in Section VII.8, making all the appropriate simplifications due to G's being bipartite and the use of rho(B) instead of delta(B).

#### Chapter IX: Polynomials Associated with Graphs.

- Description: Algebra of deletion-contraction invariants of graphs.
- Coverage: We omit Section IX.3, except that you should learn the very important Theorem IX.39 and its lovely proof.
*Additional definitions.*- Tutte's terminology is outdated and very nonstandard. Normally, one would say that a
*function*of graphs is any function whose domain is the class of all graphs. An*invariant*of graphs is a function defined on graphs such that if G and H are isomorphic, then f(G) = f(H). A function need not be invariant. - A more modern term for a V-function is a
*Tutte invariant of graphs*. - If you want descriptive names, the four defining properties of a Tutte invariant can be called (o)
*Invariance*, (i)*Normalization*, (ii)*Multiplicativity*, and (iii)*Additivity*. - Another name is that we might call
**R**_{G}(**s**) the*universal Tutte invariant*of G. - I type
**R**as a substitute for R with a tilde, which I can't do in HTML. - Given an infinite sequence
**a**= (a_{0}, a_{1}, a_{2}, ...), its*binomial transform*, written B**a**, is the sequence**b**= (b_{0}, b_{1}, b_{2}, ...) defined by

b_{j}= Sum_{(i = 0 to infinity)}(j choose i) a_{i}.

Its*inverse binomial transform*is the sequence**c**= (c_{0}, c_{1}, c_{2}, ...) defined by

c_{j}= Sum_{(i = 0 to infinity)}(-1)^{j-i}(j choose i) a_{i}.

- Tutte's terminology is outdated and very nonstandard. Normally, one would say that a
*Problems.*Hand in ## 1 - 3, 6 - 15.- In ## 2, 3, one graph in each is sufficient. I sugggest you use the same graph in # 2 as you do in # 3 (instead of Tutte's suggested graphs for # 2); but you may prefer Tutte's graphs. There are at least three ways to solve # 3: by coloring, by induction using Tutte invariance, by using other computational theorems, and by substitution in
**R**_{Wn}(**s**) ; I recommend doing all of the first three (but not the fourth since it seems impractically long).

- In Section IX.6 Tutte claims that certain linear relations hold for |E(G)| > n. Do they also hold for |E(G)| = n ? |E(G)| = n-1 ? Give a proof or counterexample. Concentrate on n = 1, 2, 3.
- Prove that F(G), the number of maximal forests in G, satisfies the additive law of Tutte invariants.
- Prove the
**Binomial Inversion Theorem**: Given sequences**a**and**b**. Then**b**is the binomial transform of**a**if and only if**a**is the inverse binomial transform of**b**. - In connection with the universal Tutte invariant, what can you say about f(G) = the number of all spanning forests in G ?
- Suppose G is the union of subgraphs H and K whose intersection is the single vertex x. (We call G the
*one-point amalgamation*of H and K.) The question is how to express**R**_{G}(**s**) by a formula similar to

**R**_{G}(**s**) =**R**_{H}(**s**)**R**_{K}(**s**) /**R**_{X1}(**s**)

(which may be correct or incorrect). - Prove that
**R**_{G}(**s**), regarded as a polynomial in the variables**t**defined by t_{m}= R_{Xm}(**s**), has no constant term, unless G is the null graph. - Theorem IX.8 is true if R is an integral domain but in general it is false. (Produce a proof and a counterexample.)
- Prove the correct general version of Theorem IX.8:
**Theorem IX.8'**. A Tutte invariant f is topologically invariant if and only if

(1+t_{0}) t_{m}= 0 for all m >= 0,

where t_{m}denotes f(X_{m}). - This problem consists of two related but independent questions about the dichromatic polynomial.
- Compute Q
_{Kn}(u,v) for n = 1, 2, 3, ..., as far as seems reasonable. - If G = H union K, where H intersect K = a complete graph K
_{n}, then can you express Q_{G}in terms of Q_{H}and Q_{K}? Try for n = 2 especially (G is called the*edge amalgamation*of H and K). Try larger n as far as you reasonably can. (Generalization of Theorems IX.9 and IX.27.)

- Compute Q
- A "snark" is defined to exclude graphs with a bond of 2 or 3 edges, because their snarkiness is derived from that of a residual graph, H
_{1}or K_{1}. That is, positivity of phi(4) for such a graph is derivable from positivity for its residual graph(s). Can you compute the actual value of phi_{G}(4) from phi_{H1}(4) and phi_{K1}(4) in the case of a bond of 2 or 3 edges?

- In ## 2, 3, one graph in each is sufficient. I sugggest you use the same graph in # 2 as you do in # 3 (instead of Tutte's suggested graphs for # 2); but you may prefer Tutte's graphs. There are at least three ways to solve # 3: by coloring, by induction using Tutte invariance, by using other computational theorems, and by substitution in

#### Matroids.

- Description: Quick introduction to matroids.
*Problems.*Hand in: none.- Out of the six aspects of matroids I presented in class, pick a first one (e.g., independent sets) and another (e.g., rank); write down the conversion rule that defines the second aspect in terms of the first (e.g., define rank in terms of independent sets), and prove that the defining propoerties of the first aspect imply those of the second aspect. Do this for as many pairs as you like.
- Let M
_{1}and M_{2}be matroids with disjoint point sets E(M_{1}) and E(M_{2}).- Prove that their direct sum M, as defined in class (by independent sets of rank), is a matroid.
- Prove that the definition via independent sets implies that by rank, and vice versa.

- Deduce from the definition of direct sum in terms of independent sets a definition in terms of some other aspect of matroids, aside from rank.
- Let M be a matroid and S a subset of E = E(M). Using the definitions from class by either independent sets or rank:
- Prove that the restriction M|S is a matroid.
- Prove that the contraction M/S is a matroid.

- Let M be a matroid and S a subset of E = E(M). Prove the equivalence of the definitions by independent sets and rank of
- the restriction M|S;
- the contraction M/S.

- Let M be a matroid and S a subset of E = E(M). Starting with the definitions from class by independent sets, give (with proofs, of course) descriptions in terms of some other aspect of matroids (aside from rank) of
- the restriction M|S;
- the contraction M/S.

- Prove that, if G is a graph and M(G) its matroid and S is a subset of E(G), then
- M(G)|S = M(G|S);
- M(G)/S = M(G/S).

#### The Tutte Polynomial and Tutte Invariants of Matroids.

- Description: Algebra of deletion-contraction invariants of matroids.
- Reading: Sections 1, 2, 4, 5 of "The Möbius function and the characteristic polynomial" by T. Zaslavsky, Ch. 7 in Combinatorial Geometries. This will be distributed in class. Note that the "dichromate" is now universally called the
*Tutte polynomial*, with the letter t or T instead of chi. *Problems.*Hand in: none. If you want some elementary exercises, see some of those in the exercise list of the chapter.*Presentations.*Most of these are a theorem with its proof (obligatory!) and maybe an example. The time for one presentation should be**at most**20 or 30 minutes.**[IA]**Belk

The incidence algebra of a poset: p. 115, ¶2 and Prop. 7.1.2.**[MI]**Pallekonda

Möbius inversion: p. 116, ¶2 and Prop. 7.1.3.**[BXmu]**Polo

The Boolean expansion formula for the Möbius function and the example: p. 117, Prop. 7.1.4 and Ex. 7.1.5.**[C]**Bowlin

The covering theorem: p. 115, Prop. 7.1.6.**[TGmup]**TZ

T-G invariance of the Möbius invariant and characteristic polynomial: p. 118, Theorem 7.1.7, and p. 121, Theorem 7.2.4.**[RS]**Wassink

Rota's sign theorem: pp. 118-119, Theorem 7.1.8. (This uses [C].)**[BXp]**Lubovsky

Boolean expansion of the characteristic polynomial: pp. 120-121, Prop. 7.2.1 and Ex. 7.2.2.**[TGr]**Ferry

T-G invariance of the rank generating polynomial: p. 126, Prop. 7.4.1.**[U]**Loftus

Universality of the rank generating polynomial: p. 127, Prop. 7.4.2.**[CP]**Roy

Chromatic polynomial: pp. 127-128, Prop. 7.5.1. (This uses [MI].)**[PL]**Findik

The partition lattice: p. 129, example with formula (7.9). Maybe, take a look at Exercise 7.4.- Appropriate parts of some of the exercises on matroids are also possible presentations.

To my home page.