Math 580: Topics in Combinatorics
Graphs and Combinatorial Invariants
(Ideas of W.T. Tutte)

The Combinatorics Seminar

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.)

Course Procedure

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.)

Due Dates

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.

Syllabus and Assignments

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.
    4. 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₁, ..., V_k be the equivalence classes. (b) Prove: Theorem B. The components of G are precisely the subgraphs G[V_i].
    5. 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.)
    6. Prove that, if e is an isthmus of G and f is an isthmus of G - e, then f is an isthmus of G.
    7. 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.
    8. 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₂({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₅ .)
       1. Show that P is the Petersen graph (see Fig. IV.2.8, right).
       2. Show that P has exactly 120 automorphisms.
       3. 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.
       4. Is the same true of 4-arcs?

• Chapter II: Contractions and the Theorem of Menger.

  • Description: More basics; and famous theorems.
  • Problems. Hand in ## 2, 3 (optional), 4, 6, 7.
    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).
    8. 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.

• Chapter III: 2-Connection.

  • Description: Basic structure theory.
  • Problems. Hand in ## 1 - 4.
    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₂ (or just possibly one or two other exceptional cases that I missed).

• 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.
    1. Make it interesting! Do it so there exist edges of all three types, insofar as you can.
    5. 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).
    6. 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
       1. every other deficient (unfilled) vertex is inaccessible by J(r)-paths and
       2. delta(r) = 1 or r is unicursal.
       Suppose (1) and (2) are true with respect to a particular deficient "center" vertex r. Question: Is it impossible to improve F by changing to some other center r' and applying Tutte's algorithm from r' ?
    7. 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.
       1. f equals 1 for all but two vertices, at which it equals 2. (There are 2 such functions up to isomorphism. Pick one.)
       2. f equals 1 for all vertices but two nonadjacent ones, at which it equals 3.
    8. 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.
    9. (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₃ , 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₃ if and only if it has a 1-factor.
    10. Does Petersen's Theorem characterize the simple cubic graphs that have a 1-factor?
    11. 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) }.
    12. Prove Theorem VII.33.
    13. Write out a complete proof of Hall's Theorem (II.39) from Theorem VII.35.
    14. 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₀, a₁, a₂, ...), its binomial transform, written Ba, is the sequence b = (b₀, b₁, b₂, ...) defined by
          b_j = Sum_{(i = 0 to infinity)} (j choose i) a_i .
      Its inverse binomial transform is the sequence c = (c₀, c₁, c₂, ...) defined by
          c_j = Sum_{(i = 0 to infinity)} (-1)^j-i (j choose i) a_i .
  • Problems. Hand in ## 1 - 3, 6 - 15.
    1. 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).
    8. 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.
    9. Prove that F(G), the number of maximal forests in G, satisfies the additive law of Tutte invariants.
    10. 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.
    11. In connection with the universal Tutte invariant, what can you say about f(G) = the number of all spanning forests in G ?
    12. 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).
    13. 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.
    14. Theorem IX.8 is true if R is an integral domain but in general it is false. (Produce a proof and a counterexample.)
    15. 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₀) t_m = 0 for all m >= 0,
        where t_m denotes f(X_m).
    16. This problem consists of two related but independent questions about the dichromatic polynomial.
        1. Compute Q_Kn(u,v) for n = 1, 2, 3, ..., as far as seems reasonable.
        2. 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.)
    17. 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₁ or K₁ . 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?

• Matroids.

  • Description: Quick introduction to matroids.
  • Problems. Hand in: none.
  1. 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.
  2. Let M₁ and M₂ be matroids with disjoint point sets E(M₁) and E(M₂).
     1. Prove that their direct sum M, as defined in class (by independent sets of rank), is a matroid.
     2. Prove that the definition via independent sets implies that by rank, and vice versa.
  3. 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.
  4. Let M be a matroid and S a subset of E = E(M). Using the definitions from class by either independent sets or rank:
     1. Prove that the restriction M|S is a matroid.
     2. Prove that the contraction M/S is a matroid.
  5. 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
     1. the restriction M|S;
     2. the contraction M/S.
  6. 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
     1. the restriction M|S;
     2. the contraction M/S.
  7. Prove that, if G is a graph and M(G) its matroid and S is a subset of E(G), then
     1. M(G)|S = M(G|S);
     2. 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.
    1. [IA] Belk
       The incidence algebra of a poset: p. 115, ¶2 and Prop. 7.1.2.
    2. [MI] Pallekonda
       Möbius inversion: p. 116, ¶2 and Prop. 7.1.3.
    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.
    4. [C] Bowlin
       The covering theorem: p. 115, Prop. 7.1.6.
    5. [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.
    6. [RS] Wassink
       Rota's sign theorem: pp. 118-119, Theorem 7.1.8. (This uses [C].)
    7. [BXp] Lubovsky
       Boolean expansion of the characteristic polynomial: pp. 120-121, Prop. 7.2.1 and Ex. 7.2.2.
    8. [TGr] Ferry
       T-G invariance of the rank generating polynomial: p. 126, Prop. 7.4.1.
    9. [U] Loftus
       Universality of the rank generating polynomial: p. 127, Prop. 7.4.2.
    10. [CP] Roy
        Chromatic polynomial: pp. 127-128, Prop. 7.5.1. (This uses [MI].)
    11. [PL] Findik
        The partition lattice: p. 129, example with formula (7.9). Maybe, take a look at Exercise 7.4.
    12. Appropriate parts of some of the exercises on matroids are also possible presentations.

To my home page.