Lec 1 8/22 Wed: overview sample of topics in course

Lec 2 8/24 Fri Sec 1.1: spanning trees with many leaves (min degree 3,
general min degree), Huffman coding (Shannon bound skipped)

Lec 3 8/27 Mon Sec 1.1-1.2: optimal alphabetic trees (dynamic programming,
Hu-Tucker algorithm), eccentricity/radius/diameter (center confined to block,
Moore bound, Hoffman-Singleton graph)

Lec 4 8/29 Wed Sec 1.2:
small graphs with fixed order/diameter/maxdegree, oriented diameter construction

Lec 5 8/31 Fri Sec 1.2:
oriented diameter (Chvatal-Thomassen bound), diameter vs. average distance,
diameter vulnerability, connected domination (independence bound)

Lec 6 9/5 Wed Sec 1.2-3:
independence bound on average distance, squashed cube embeddings (examples)

Lec 7 9/7 Fri Sec 1.3:
squashed cube dimension (lower and upper bound),

Lec 8 9/10 Mon Sec 1.3:
bandwidth: density bound (caterpillar sketch),
boundary bound (grids), Sperner's Lemma (triangular grid),
mention of edge bandwidth (*B'(G) >B(G)*) and edge addition

Lec 9 9/12 Wed Sec 2.1:
Hall's Theorem with lower bound on #matchings,
Birkhoff-von Neuman Theorem and rancher/farmer problem,
Ore's defect formula, Konig-Egervary Theorem, min/max relations

Lec 10 9/14 Fri Sec 2.1
Tutte 1-factor Theorem, Berge-Tutte Formula,
Berge generalization of Petersen's Theorem,
Gallai-Edmonds Structure Theorem

Lec 11 9/24 Mon Sec 2.2:
augmenting paths, fast bipartite matching, Edmonds' Blossom algorithm

Lec 12 9/25 Tue Sec 2.2:
weighted matching, on-line ski rental, on-line matching deterministic

Lec 13 9/26 Wed Sec 2.2: on-line matching randomized
(performance of RANDOM, upper bound for randomized algorithms, statement
of RANKING)

Lec 14 9/28 Fri Sec 2.3:
*f*-factor reduction, necessity of *f*-factor condition
Tutte *f*-Factor Theorem

Lec 15 10/01 Mon Sec 2.3-4:
Parity Lemma, Erdos-Gallai conditions, Kundu's Theorem,
, comments on
general factor problem and complexity,
stable sets and vertex covers (Gallai's Theorem, Konig's Other Theorem)

Lec 16 10/02 Tue Sec 2.4:
maximum stable sets (alternating-list characterization), greedy algorithms,
Caro-Wei Theorem (brief),
beta-critical edges, Bondy bound on vertex cover number

Lec 17 10/03 Wed Sec 2.4:
independence ratio in cubic triangle-free graphs,
domination number (Arnautov-Payan bound),

Lec 18 10/08 Mon Sec 2.4: edge bound for fixed domination number,
odd dominating sets, independent domination in claw-free graphs,
kernels in digraphs.

Lec 19 10/09 Tue Sec 2.4-3.1: covering numbers and total domination of Kneser
graphs, chromatic number and coloring examples (assumed),
Minty's theorem (postponed to circular coloring).
generalized coloring (Ok,Sk,Dk,Ck), k-greedy coloring.

Lec 20 10/10 Wed Sec 3.1: Matula generalization of Brooks,
Lovasz max degree coloring

Lec 21 10/12 Fri Sec 3.2:
Descartes girth 6 & large chromatic number,
hypergraph coloring, construction for large
chromatic number & girth, edge-connectivity of color-critical graphs

Lec 22 10/15 Mon Sec 3.2:
Color-critical: generalized Hajos construction, minimum excess degree
(Dirac, Gallai)

Lec 23 10/16 Tue Sec 3.2: broom-free graphs weakly chi-bounded, K_4-subdivision
(Dirac), Hajos and Hadwiger conjectures, min degree for F-subdivision

Lec 24 10/17 Wed Sec 3.3: review of basic edge-coloring results
through Vizing-Gupta and Anderson-Goldberg, overfull/1-factorization
conjectures, Vizing Adjacency Lemma

Lec 25 10/19 Fri Sec 3.3:
Erdos-Faber-Lovasz reduction, Chang-Lawler coloring of linear hypergraphs

Lec 26 10/22 Mon Sec 3.4:
List coloring (review degree-choosability through list version of Brooks),
relation between bipartite choosability and 2-coloring hypergraphs

Lec 27 10/24 Wed Sec 3.4: lower bound by average degree (Alon), list coloring
conjecture, Galvin's List Color Theorem

Lec 28 10/26 Fri Sec 3.4: list version of Shannon, f-choosability,
3-choosability of planar bipartite

Lec 29 10/29 Mon Sec 3.4: C_n^2 3-choosability, Alon-Tarsi Theorem

Lec 30 10/31 Wed Sec 3.5: circular and (k,d)-coloring through
sufficient cond for chi_c=chi

Lec 31 11/02 Fri Sec 3.5: chi_c small, graph homomorphisms

Lec 32 11/05 Mon Sec 4.1: perfect graph intro, classical examples,
the Perfect Graph Theorem

Lec 33 11/07 Wed Sec 4.1: perfectly orderable graphs, star-cutset lemma,
comments on Meyniel graphs and weakly chordal graphs

Lec 34 11/09 Fri Sec 4.2-3: comments on partitionable graphs and Strong Perfect
Graph Theorem, chordal graphs (simplicial vertices, vertex separators, clique
trees)

Lec 35 11/12 Mon Sec 4.3: chordal graph recognition by MCS, comments on split,
strongly chordal/bichordal graphs

Lec 36 11/14 Wed Sec 4.3: characterizations of interval graphs, comments on
threshold, unit interval, threshold, parity

Lec 37 11/16 Fri Sec 5.1: Turan's Theorem, counting triangles (through
Moon-Moser), further comments on *k_p(G)*

Lec 38 11/26 Mon Sec 5.1: Erdos-Stone by Regularity Lemma and Embedding Lemma

Lec 39 11/28 Wed Sec 5.1: lemmas for Regularity Lemma

Lec 40 11/30 Fri Sec 5.1-2: completion of proof of Regularity Lemma,
application to linear Ramsey number for bounded-degree graphs,
skipped induced Turan problems and anti-Ramsey numbers

Lec 41 12/03 Mon Sec 5.2-3:
Ramsey number for paths, extremal decomposition problems
(into complete graphs, forests (mention arboricity), trees)

Lec 42 12/05 Wed Sec 5.3-4: mention linear arboricity, Lovasz path/cycle
decomposition (sketch), intersection number, boxicity

Lec 43 12/07 Fri Sec 5.4: interval number, total interval number, visibility
number