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