MATH 581 / CS 572

EXTREMAL GRAPH THEORY, Spring 2006

Summary of Lectures

This page contains a summary of the lectures in this course for Spring 2006. 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/18 Wed: overview sample of topics in course
Lec 2 1/20 Fri Sec 1.1: spanning trees with many leaves (min degree 3, general min degree)
Lec 3 1/23 Mon Sec 1.1: Huffman coding, Shannon's Theorem, optimal alphabetic trees (dynamic programming, Hu-Tucker algorithm)
Lec 4 1/25 Wed Sec 1.2: eccentricity/radius/diameter, center confined to block, Moore bound, Hoffman-Singleton graph, small graphs with fixed order and diameter and maximum degree, lower bound for oriented diameter.
Lec 5 1/27 Fri Sec 1.2: oriented diameter (Chvatal-Thomassen bound), diameter vs. average distance, diameter vulnerability, connected domination (independence bound)
Lec 6 1/30 Mon Sec 1.3: independence bound on average distance, squashed cube embeddings squashed cube dimension (eigenvalue lower bound example)
Lec 7 2/1 Wed Sec 1.3: squashed cube dimension (lower and upper bound), bandwidth introduction
Lec 8 2/3 Fri Sec 1.3: bandwidth (boundary bound, grids, Sperner Lemma/simplex, density bound & caterpillars, upper bounds for edge addition)
Lec 9 2/6 Mon Sec 1.3: bandwidth (lower bound for edge addition), edge-bandwidth (B'(G) >= B(G))

Lec 10 2/8 Wed Sec 2.1: bipartite matching (Hall's Theorem with lower bound on #matchings, Ore's min-max formula, Konig-Egervary Theorem), matching in general graphs (Tutte 1-factor Theorem, initial applications skipped)
Lec 11 2/10 Fri Sec 2.1: Gallai-Edmonds Structure Theorem, counting 1-factors in k-connected graphs, (skipped Van der Waerden)
Lec 12 2/13 Mon Sec 2.2: augmenting paths, fast bipartite matching, Edmonds' Blossom algorithm, weighted matching
Lec 13 2/15 Wed Sec 2.2: on-line ski rental, on-line matching (deterministic algorithms, performance of RANDOM, upper bound for randomized algorithms)
Lec 14 2/17 Fri Sec 2.2-3: on-line matching (RANKING vs. EARLY), f-factor reduction, necessity of f-factor condition
Lec 15 2/20 Mon Sec 2.3: Tutte f-Factor Theorem, Parity Lemma
Lec 16 2/22 Wed Sec 2.3: Erdos-Gallai conditions, Kundu's Theorem, toughness & k-factors (state results), general factor problem
Lec 17 2/24 Fri Sec 2.4: stable sets and vertex covers (Gallai's Theorem, Konig's Other Theorem, alternating-list characterization, greedy algorithms, Caro-Wei Theorem)
Lec 18 2/27 Mon Sec 2.4: beta-critical edges, Bondy bound on vertex cover number, independence ratio in cubic triangle-free graphs, domination number (Arnautov-Payan bound)
Lec 19 3/01 Wed Sec 2.4: edge bound for fixed domination number, independent domination in claw-free graphs, kernels in digraphs, odd dominating sets

Lec 20 3/03 Fri Sec 3.1: vertex coloring examples, Minty's theorem, generalized coloring, Matula generalization of Brooks
Lec 21 3/06 Mon Sec 3.1: lemma for Matula generalization, Lovasz max degree coloring, Descartes girth 6 & large chromatic number
Lec 22 3/08 Wed Sec 3.2: hypergraph coloring, construction for large chromatic number & girth, color-critical properties, generalized Hajos construction
Lec 23 3/10 Fri Sec 3.2: minimum excess degree in color-critical graphs (Dirac, Gallai), introduce chi-bounded families
Lec 24 3/13 Mon Sec 3.2: broom-free graphs weakly chi-bounded, K_4-subdivision (Dirac), Hajos and Hadwiger conjectures, min degree for F-subdivision
Lec 25 3/15 Wed Sec 3.3: review of basic edge-coloring results (without proofs) up to Vizing-Gupta and Anderson-Goldberg, overfull/1-factorization conjectures, Erdos-Faber-Lovasz reduction, start edge-coloring of linear hypergraphs
Lec 26 3/17 Fri Sec 3.3-4: Chang-Lawler bound on coloring of linear hypergraph, review of basic list coloring results (degree-choosability, etc.)
Lec 27 3/27 Mon Sec 3.4: lower bound by average degree (Alon), list coloring conjecture, Galvin's Theorem
Lec 28 3/29 Wed Sec 3.4: 3-choosability of planar bipartite, Alon-Tarsi
Lec 29 3/31 Fri Sec 3.4-5: precoloring extension, circular coloring
Lec 30 4/03 Mon Sec 3.5: (k,d)-coloring, sufficient cond for chi_c=chi
Lec 31 4/05 Wed Sec 3.5: chi_c small, graph homomorphisms, start perfect graphs

Lec 32 4/06 Thu Sec 4.1: the Perfect Graph Theorem, perfectly orderable graphs
Lec 33 4/07 Fri Sec 4.1: star-cutset lemma, comments on Meyniel graphs and weakly chordal graphs
Lec 34 4/10 Mon Sec 4.2: comments on partitionable graphs and Strong Perfect Graph Theorem
Lec 35 4/12 Wed Sec 4.3: chordal graphs (characterizations, properties, and recognition)
Lec 36 4/13 Thu Sec 4.3: comments on strongly chordal/bichordal graphs, characterization of interval graphs
Lec 37 4/14 Fri Sec 4.3: unit interval, threshold, tolerance, and parity graphs

Lec 38 4/17 Mon Sec 5.1: Turan's Theorem, counting triangles (through Moon-Moser), comments on graph Ramsey theory
Lec 39 4/19 Wed Sec 5.2: Ramsey number for paths, start linear Ramsey number for bounded-degree graphs
Lec 40 4/21 Fri Sec 5.2: linear Ramsey for bounded degree, start anti-Ramsey number for cycles
Lec 41 4/24 Mon Sec 5.2-3: anti-Ramsey for C4, greedy clique decomposition, arboricity (state only), decomposition into trees
Lec 42 5/01 Mon Sec 5.3-4: linearity arboricity (state only) Lovasz path/cycle decomposition (sketch), intersection number, boxicity
Lec 43 5/03 Wed Sec 5.4: interval number, total interval number, visibility number