TOPICS OF FUTURE LECTURES ARE SUBJECT TO CHANGE WITHOUT NOTICE
Lecture 1: Eulerian Paths. First chapter of the text. We also showed that we could determine the minimum number of arcs we needed to reverse to make an orientation Eulerian in polynomial time by reducing this problem to Min cost flow. We then discussed a paper on counting Eulerian Orientations which is not examined material.
Lecture 2. Hamilton Cycles Second Chapter of the text and the proofs of the Theorems of Dirac,Posa, and Ore. See this article for the statements and a proof of Dirac's theorem similar to that given in class (you need only read the section entitle Dirac's Theorem).
Lecture 3. Planar Graphs Fifth Chapter of the text and supplementary material We proved Eulers' Formula, Kuratwoski's Theorem, and Whitney's Theorem. We discussed How Cauchy's result on the classification of regular solids follows from the first of these. The proofs of the latter two results can be found in Chapter three of the Rooted Routing Manuscript. This lecture took two classes.
Lecture 4 and 5: Minors and Routing. We defined graph minors, charcterized graphs without K_5 minors. Discussed the characterization of $K_l$ minors for graphs without a $k_l$ minor for arbitrary $l$. We defined the rooted routing problem, showed how to solve the 2-path case and discussed how our characterization would help solve it in general. This material is also in the first three chapters of my rooted routing manuscript.
Lecture 6. The Influence of Chemistry and Algebra. Chapters 3 and 4 in the text. We didn't cover all the material in these chapters. We defined trees and isomorphisms and proved that there are n to the n-2 labelled trees on $n$ nodes using Prufer sequences. We also defined the centroid and bicentroid of a tree and proved thar every tree has one or the other. Ditto for center-bicenter.
Lecture 7. Graph Colouring including The Four Colour Conjecture, Hadwiger's conjecture, and Brook's Theorem. Chapters 6 of the text, Sections 1.1, 1.2, and 1.7 of my book with Molloy.
Lecture 8. Factors in Graphs Chapter 10 in the text and supplementary material We proved that the minimum deficiency of a matching M (def(M)=|V|-2|M|) is equal to the maximum over all sets $Z$ of the number of odd ccomponents of G-Z minus |Z|. We saw a second algorithmic proof where we mimiced the bipartite case, shringing an odd cycle into a super vertex if necessary. This is also a polynomial time algorithm. Both these proofs relied on the fact that a matching is maximum if and only if there is no augmenting path for it. We started the proof of Vizing's theorem.
Lecture 9. Ideas From Linear Programming Better take notes today. We talked about graph parameters being solutions to IPs, and discussed fractional parameters which were relaxations of these IPs to LPs. Some parameters have dual fractional variants. e.g. fractional colouring and fractional clique. Sometime the IPs are equal, e.g. max number of disjoint s-t paths, min size of a cut. We can sometimes solve these fractional relaxations using Linear Programming, using the ellipsoid method and the fact that separation is equivalent to optimization. We gave as an example of a fractional parameter the fractional total chromatic number which we saw was at most Delta+3. If the integrality gap is not too large, this tells us something about the integer parameter. For example we saw that there is an optimal fractional matching which is half integral and used this to show that the optimal LP solution value is at most 3/2 of the optimal IP solution value. We showed how fractional edge colouring reduced to determining the matching polytope and gave a characterization of this polytope.
Lecture 10. The influence of Algebra and Topology Chapter 8 in the text and supplementary material We shaw how the study of cycle bases for graphs and geometric duality led Whitney to the definition of a matroid. We finished off our factors in graphs stuff, completing the proof of Vizing's Theorem and discussing Tutte's F-factor theorem.
Lectures 11 Introduction to Perfect Graphs We defined the Shannon Capacity of a graph and noted that it lay between the maximum stable set size and the clique cover number. This motivated the definition of perfect graphs. As a second motivation, we proved that the polytope
$$ \x \ge 0, ~~\forall S \in {\cal S}(G) \sum_{v \in S} x_v \ge 0$$
has only integer vertices if $G$ is perfect (there is a sense in which this is if and only if). To do so, we used the following two facts:
(1) $G$ is perefect precisely if in every vertex induced subgraph $H$ there is a stable set meeting all the maximum cliques.
(2) Every graph obtained by replicating a vertex in a perfect graph is perfect.
We then proved that every triangulated graph (a graph with no induced cyclke of length at least four) is a clique or has a clique cutset. This allowed us to prove that every such graph contains a simplical vertex. Thus we can use an intelligent greedy algorithm to colour using $\omega(G)$ colours (colour a simplicial vertex last). Furthermore, ripping out a simplicial vertex and its neighbourhood shows that the clique cover number and the maximum stable set size are equal. I.e. the complements of triangulated graphs are perfect.
We saw that Bipartite graphs are trivially perfect and their complements are perfect as an optimal olouring corresponds to a maximum matching.
We saw that Comparability graphs are perfect because we can colour a vertex with the length of the longest path into it. Their complements are perfect by Dilworth's theorem.
These examples motivated two conjecture of Berge:
The WPGC: $G$ is perfect precisely if its complement is.
The SPGC: $G$ is perfect precisely if neither $G$ nor $\overline(G)$ contains an induced odd cycle of length at least five.
The first of these conjectures was proved by Lovasz in 1972. The second by Chudnovsky, Robertson, Seymour, and Thomas in 2004. We gave the proof of the first using the replication lemma and the fact stated just before it. The two book chapters handed out in class contain all this material.
Lecture 12: We discuseed clique trees and clique separable graphs. See: this article
Lecture 13: We discussed decomposing comparability graphs using homogeneous sets. The assignment writeup and a handout from Golumbic's book cover this topic. We introduced the notions of skew cutsets and star cutsets. (Then in Lecture 16) We proved that minimal imperfect graphs cannot contain star cutsets or even pairs. We saw that if we contract an even pair in a graph then we get a graph with the same clique number and chromatic number and discussed how we could use this to develop fast algorithms for optimizing in perfect graphs. The even pair material is covered in Sections 4.1 and 4.2 of the perfect graph book. Ask Louigi ir email me if you don't have notes for the star cutset proof. I also covered some unexamined material on the proof of the SPGC and gave out a handout on it.
Lectures 14-16 Tree Decompositions Need to know from handout: Chapter 8 except for the bit of Section 8.3 which proves that walls actually contain brambles of order h+2. Chapter 9 except for the bit on pathwidth, e.g from the paragraph on page 114 beginning In contrast to Lemma 9.28 The approximate Duality theorem from Chapter 10, but not Section 10.1. The first four pages of Chapter 13 and the first four pages of Chapter 14. You also need to know how to apply the Excluded Grid Minor Structure Theorem to obtain results on the Erdos-Posa property for the family of cycles.
Lectures 17-19: Graph Colouring via the probabilistic method Reference: Handouts from the book Graph Colouring via the probabilistic method. We first discussed applications of the First Moment Method and Chernoff bounds. We bound the clique size of a random graph using the first moment method. We also proved that a.a.s. every degree is within root n log n of n/2 and the union of the neighbourhood of any two vertices is within the same amount of 3n/4. We combined the latter result with an assignment problem to show that almost every graph is Hamiltonian. We used the former result to prove that Hajos's conjecture is false. We also proved a result on triangle-free graphs with high chromatic number. Finally we proved a weakining of Hadwiger's comjecture: If G has no K_l minor then it has a 100 l log l colouring. References are: Intro to Chapter 3 and section 3.2, Chapters 5 and 6. Next we discussed the Local Lemma and its application to Total Colouring, References are Chapters 4 and 7.