Spring 2012

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.

Graph Theory by Reinhard Diestel, fourth edition (Springer-Verlag, 2010). The text can be read on line; there are also the table of contents, a cheap student PDF, etc.

We will cover as many chapters as we can, which is possibly about six to eight.

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

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

To my home page.