MATH 581 / CS 572

EXTREMAL GRAPH THEORY, Fall 2007

Summary of Lectures

This page contains a summary of the lectures in this course for Fall 2007. 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 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