Spring 2008

To the schedule and assignments | additional problems page | student presentations page.

The course is for students in the second year and higher; it is not an introductory graduate course. The absolute minimum requirement is a good understanding of abstraction and a solid modern algebra background (as from a graduate course), and the more graduate math you know, the better (that's the famous "mathematical maturity"). If you aren't sure whether you might be interested or ready for this class, please see me.

We will use the textbook Graph Theory by Reinhard Diestel, third edition (Springer-Verlag, 2005). The text can be read on line. We will cover as many chapters as we can, which is probably about six. Here is a link to the table of contents. Here is a link to Diestel's list of errata. Here is the link to my list of errata (below, on this page).

I will expect you to study the material and to work on as many of the exercises as you can. I will meet separately with each student frequently (every week, I hope) to discuss your progress and any questions you or I may have.

HOMEWORK: I will frequently collect written work: see the homework assignments.

- I expect you to try (almost) every hand-in problem (as well as other problems). If you can't solve the problem but you have some work that makes sense, write it up and turn it in.
- I will accept a
**second version**of any problem, if you want to rewrite it for a better grade (or any other reason), but only within a reasonable time (let's say, about two weeks from when I returned the first version). - Also, if you don't turn in a problem by the due date, I will accept a late paper (within a reasonable time, about two weeks), but I won't usually allow rewrites of late problems.
- If you have an emergency, be sure to tell me so I can adjust the requirements as necessary.

We meet on MWF 1:10 - 2:10 in LN-2205.

Office hours MWF 2:30 - 3:30, but I will usually be around much later on MWF afternoons, so stop in if you wish.

**Special class times:**

Th 2/7 at noon in LN-2205.

Th 3/13 at noon in LN-2205.

Th 4/10 at noon in LN-2205.

Th 4/17 at noon in LN-2205.

Th 4/24 at noon in LN-2205.

Th 5/1 at noon in LN-2205 **instead of** F 5/2.

The Combinatorics Seminar meets on Tuesdays at 1:15 in LN-2205. (Occasionally at a different time; check the schedule.) All 510 students are invited to attend (if the room is big enough for 510 students—Sorry, bad old joke, slap).

To the schedule and assignments | additional problems page | student presentations page.

- Synonym lists:
- Cycle, circuit, circle, polygon. These are names for a (nonempty) connected edge set with all degrees equal to 0 or 2 (this is what the book would call a "cycle").

- The
*oriented incidence matrix*is the V × E matrix H(G) in which the column corresponding to edge e has one +1 and one −1 in the rows corresponding to the endpoints of e, with 0's elsewhere. (We rarely have to worry about the choice of which endpoint gets which sign; we can just make an arbitrary choice and stick to it.) This definition works for multigraphs without loops. The matrix defined in the book, with only +1's, is the*unoriented incidence matrix*. - An
*algebraic cycle*of G*over*F (where F is a field) is an element of the*cycle space*of G over F, which is defined to be the null space Nul H(G) (also called Z_{1}(G; F), especially in algebraic topology). An*(algebraic) cocycle*is an element of the*cocycle space*, which is defined to be the orthogonal complement of the cycle space, i.e., it is the row space Row H(G). A*binary cycle*or*cocycle*is an algebraic cycle with F =**F**_{2}, or equivalently the corresponding subset of E. - A
*signed graph*is a graph whose edges are labelled positive or negative. Thus, it is Σ = (G, σ) where σ: E -> {+,−}.- A subgraph is
*balanced*if every circuit in it is positive. If all the signs are negative, a balanced subgraph is a bipartite subgraph. If all signs are positive, a balanced subgraph is any subgraph. *Switching*a vertex set X in a signed graph means reversing the sign of every edge that has one endpoint in X and the other in V \ X. Switching X is equivalent to switching each vertex in X separately (in any order).- Coloring a signed graph is done with signed colors. For a signed k-coloring, the color set is C
_{k}= {0, ±1, ±2, ..., ±k}. For a zero-free k-coloring, the color set is C_{k}\ {0}. A coloring γ is*proper*if, for each edge e_{vw}, we have

γ(v) ≠ σ(e_{vw})γ(w). The*chromatic polynomial*χ_{Σ}(2k+1) is defined, for k = 1, 2, ..., to be the number of proper signed k-colorings. The number that are zero-free, written χ_{Σ}*(2k), gives the*zero-free chromatic polynomial*.

- A subgraph is
- The "parts" of a tree decomposition: I prefer a more distinctive name:
*nodal set*for V_{t}and "nodal subgraph" for G[V_{t}]. (I use the term "node" for a vertex of T. Generally, "node" is a synonym for "vertex" but not used much any more.)

- Page 10, Theorem 1.3.4: The theorem's meaning is not apparent from the statement. A meaningful statement would be: Given numbers d ≥ 2 and g in N, every graph G with δ(G) ≥ d and g(G) ≥ g has order |G| ≥ n
_{0}(d,g). - Page 30, # 6: There is something wrong with the statement of the second half; for instance, what do they mean by d? Can you figure out what it should be?
- Page 38: The definition of
*stable marriage*is incorrect and so are the statement and proof of the Gale-Shapley Theorem. I believe the correct definition is: a matching in which there are no two edges ab and a'b' such that a prefers b' to b and b' prefers a to a'. (You can look this up if you like; there's a book.) - Section 6.2: The so-called MFMC Theorem is actually (when combined with the corollary) the Integral MFMC Theorem, not the usual MFMC Theorem.
- Chapter 6: The terminology "k-flow" for nowhere-zero k-flow is completely nonstandard. You should always say "nowhere-zero", even though it's slightly longer.
- Chapter 12: The term "(graph) minor theorem" should be "(graph) minors theorem".

To the schedule and assignments | additional problems page | student presentations page.

To my home page.