MATH 417

EXTREMAL GRAPH THEORY, Spring 2004

Summary of Lectures

This page contains a summary of the lectures in this course for Spring 2004. It lists only the topics discussed in each lecture. The text provides extensive discussion and additional material, so no additional notes are given here.

Lec 1 1/21 Wed: overview sample of topics in course
Lec 2 1/23 Fri Sec 1.1: spanning trees with many leaves, optimal alphabetic trees (dynamic programming)
Lec 3 1/26 Mon Sec 1.1: Hu-Tucker alphabetic tree algorithm, Moore graphs, small graphs with fixed order and diameter and maximum degree
Lec 4 1/28 Wed Sec 1.2: oriented diameter, diameter vs. average distance
Lec 5 1/30 Fri Sec 1.2: average distance vs. independence number, squashed cube embeddings
Lec 6 2/2 Mon Sec 1.3: squashed cube dimension (eigenvalue lower bound, n(G)-1 upper bound)
Lec 7 2/4 Wed Sec 1.3: bandwidth (bounds, caterpillars, grids)
Lec 8 2/6 Fri Sec 1.3: bandwidth (edge addition, Sperner Lemma/simplex, brief mention of edge bandwidth)
Lec 9 2/9 Mon Sec 2.1: Hall's Theorem (with lower bound on #matchings), Birkhoff-von Neuman Theorem and rancher/farmer problem, Ore's min-max formula, Konig-Egervary Theorem
Lec 10 2/11 Wed Sec 2.1: Tutte 1-factor Theorem, Berge-Tutte Formula, Berge generalization of Petersen's Theorem
Lec 11 2/13 Fri Sec 2.1: Gallai-Edmonds Structure Theorem, counting 1-factors in k-connected graphs, (skipped Van der Waerden)
Lec 12 2/16 Mon Sec 2.2: fast bipartite matching, Edmonds' Blossom algorithm
Lec 13 2/18 Wed Sec 2.2: weighted matching, deterministic on-line problems (ski rental, matching)
Lec 14 2/20 Fri Sec 2.2: on-line matching (randomized algorithms)
Lec 15 2/23 Mon Sec 2.3: f-factor reduction, Tutte f-Factor Theorem
Lec 16 2/25 Wed Sec 2.3: Erdos-Gallai conditions, statement of other factor results
Lec 17 2/27 Fri Sec 2.4: independent sets (characterization of maximum stable sets, Caro-Wei Theorem, critical edges, triangle-free graphs)
Lec 18 3/01 Mon Sec 2.4: independent domination in claw-free graphs, etc.
Lec 19 3/03 Wed Sec 2.4: kernels in digraphs, odd dominating sets
Lec 20 3/05 Fri Sec 3.1: vertex coloring, Minty's theorem
Lec 21 3/12 Fri Sec 3.1: generalized coloring, Brooks generalization
Lec 22 3/15 Mon Sec 3.2: Lovasz max degree coloring, construction with chromatic number & girth
Lec 23 3/17 Wed Sec 3.2: broom-free graphs weakly chi-bounded, Hajos and Hadwiger, min degree for F-subdivision
Lec 24 3/18 Thu Sec 3.3: overfull/1-fac conjectures, Vizing's Theorem
Lec 25 3/19 Fri Sec 3.3-4: edge-coloring of linear hypergraphs, list coloring
Lec 26 3/29 Mon Sec 3.4: degree-choosable, Gallai/Brooks list generalization
Lec 27 3/31 Wed Sec 3.4: lower bound by average degree (Alon), list coloring conjecture, Galvin's Theorem
Lec 28 4/01 Thu Sec 3.4: 3-choosability of planar bipartite, Alon-Tarsi
Lec 29 4/02 Fri Sec 3.4-5: precoloring extension, circular coloring
Lec 30 4/05 Mon Sec 3.5: (k,d)-coloring, chi_c=chi
Lec 31 4/07 Wed Sec 3.5: chi_c small, graph homomorphisms
Lec 32 4/09 Fri Sec 4.1: perfect graph examples, the Perfect Graph Theorem
Lec 33 4/12 Mon Sec 4.1: perfectly orderable graphs, Meyniel graphs
Lec 34 4/14 Wed Sec 4.2: comments on partitionable graphs and Strong Perfect Graph Theorem
Lec 35 4/16 Fri Sec 4.3: chordal graphs (characterizations, properties, and recognition)
Lec 36 4/19 Mon Sec 4.3: strongly chordal graphs (characterizations)
Lec 37 4/21 Wed Sec 4.3: comments on bichordal, interval, threshold, tolerance, and parity graphs
Lec 38 4/23 Fri Sec 5.2: graph Ramsey theory (trees/cliques, mK3, paths)
Lec 39 4/26 Mon Sec 5.2: linear Ramsey number for bounded-degree graphs
Lec 40 4/28 Wed Sec 5.2-3: anti-Ramsey number for cycles, greedy clique decomposition
Lec 41 4/30 Fri Sec 5.3: arboricity, decomposition into trees
Lec 42 5/03 Mon Sec 5.3-4: Lovasz path/cycle decomposition, intersection number, boxicity, interval number
Lec 43 5/05 Wed Sec 5.4: interval number, total interval number, visibility number