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