MATH 581 / CS 572

EXTREMAL GRAPH THEORY, Spring 2009

Summary of Lectures

This page contains a summary of the lectures in this course for Spring 2009. It lists only the topics discussed in each lecture. The text provides extensive discussion and additional material, so no additional notes are given here.

1 1/21 Wed: overview sample of topics in course

Topic 1: Trees and Distance
2 1/23 Fri Sec 1.1: spanning trees with many leaves (min degree 3, general min degree)
3 1/26 Mon Sec 1.1: Huffman coding, Shannon bound, optimal alphabetic trees (dynamic programming, Hu-Tucker algorithm), intro to eccentricity/radius/diameter (Harary-Norman, Moore bound)
4 1/28 Wed Sec 1.2: Hoffman-Singleton graph, small graphs with fixed order/diameter/maxdegree
5 1/30 Fri Sec 1.2: oriented diameter (construction, Chvatal-Thomassen bound, sketch of diameter 2),diameter vs. average distance,
6 2/02 Mon Sec 1.2: diameter vulnerability, independence bounds on connected domination and average distance
7 2/04 Wed Sec 1.3: squashed cube dimension (examples, eigenvalue bound, Winkler's Theorem)
8 2/06 Fri Sec 1.3: bandwidth: density bound (caterpillars), boundary bound (grids), increase under edge addition, mention of edge bandwidth (B'(G)>B(G))

Topic 2: Matching and Independence
9 2/09 Mon 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
10 2/11 Wed Sec 2.1: Tutte 1-factor Theorem via Berge-Tutte Formula, Lovasz/Zaks #matchings in k-connected graphs, Plesnik 1-factor after deleting edges from k-regular
11 2/13 Fri Sec 2.1: smallest matching number in k-regular graphs, factor-critical graphs, Gallai-Edmonds Structure Theorem
12 2/16 Mon Sec 2.2: augmenting paths, fast bipartite matching, weighted matching
13 2/18 Wed Sec 2.2: Edmonds' Blossom algorithm, on-line ski rental, on-line bipartite matching (sketch of algorithms, no proofs of bounds)
14 2/20 Fri Sec 2.3: Tutte's f-Factor Theorem (reduction to 1-factors, necessity and sufficiency)
15 2/23 Mon Sec 2.3: Parity Lemma, Erdos-Gallai conditions, Kundu's Theorem, regular factors in regular graphs (Hanson-Loten-Toft)
16 2/25 Wed Sec 2.4: maximum stable sets (Berge characterization), greedy algorithms, Caro-Wei Theorem, critical edges, Bondy bound on vertex cover number.
17 2/27 Fri Sec 2.4: independence ratio in cubic triangle-free graphs (state results), domination number (Arnautov-Payan bound, Gallai edge bound for fixed domination number, odd dominating sets
18 3/02 Mon Sec 2.4: independent domination in claw-free graphs, kernels in digraphs, domination in Kneser graphs.
19 3/04 Wed Sec 2.4-3.1: covering numbers and total domination of Kneser graphs, introduction of generalized coloring parameters (Ok,Sk,Dk,Ck)

Topic 3: Basic Coloring
20 3/06 Fri Sec 3.1: k-greedy coloring, Matula generalization of Brooks, Lovasz max degree partition
21 3/09 Mon Sec 3.1: acyclic and star coloring (bounds in terms of max degree, in-coloring)
22 3/11 Wed Sec 3.1: acyclic and star coloring (Alon-McDiarmid-Reed probabilistic construction, A-C-K-K-R inductive construction, upper bound via F-reductions)
23 3/13 Fri Sec 3.2: Descartes girth 6 & large chromatic number, construction for large chromatic number & girth
24 3/16 Mon Sec 3.2: Color-critical: generalized Hajos construction, minimum excess degree (Gallai)
25 3/18 Wed Sec 3.2: broom-free graphs weakly chi-bounded, (skipped Dirac K_4-subdivision), Hajos and Hadwiger conjectures, min degree for F-subdivision
26 3/20 Fri Sec 3.3: Anderson-Goldberg (Vizing-Gupta) Theorem, (skipped overfull/1-factorization conjectures), Chvatal-McDiarmid Theorem
27 3/30 Mon Sec 3.3: Vizing Adjacency Lemma, Erdos-Faber-Lovasz reduction, Chang-Lawler coloring of linear hypergraphs

Topic 4: Refined Coloring Models & Perfection
28 4/1 Wed Sec 3.3: Summary of parity edge-coloring and interval edge-coloring (proof of elementary results, statement of others), skipped proper weighting
29 4/3 Fri Sec 3.4: List coloring (very brief review of degree-choosability through list version of Brooks), bipartite choosability vs. 2-coloring hypergraphs, Alon's lower bound by average degree.
30 4/6 Mon Sec 3.4: List coloring conjecture, Galvin's List Color Theorem, mentioned Borodin-Kostochka-Woodall list version of Shannon, f-choosability and 3-choosability of planar bipartite graphs
31 4/8 Wed Sec 3.4: 3-choosability of squares of cycles, Alon-Tarsi Theorem
32 4/10 Fri Sec 3.4-3.5: (1,2)-choosability of even trees, intro to circular coloring
33 4/13 Mon Sec 3.5: properties of circular and (k,d)-colorings, condition for chi_c=chi, Goddyn-Tarsi-Zhang generalization of Minty to circular coloring
34 4/15 Wed Sec 3.5-4.1: upper bounds on chi_c by Steffen-Zhu, Zhu (generalizing Tuza), brief intro to classical examples of perfect graphs
35 4/17 Fri Sec 4.1: The Perfect Graph Theorem, comparability, chordal, perfectly orderable graphs

Topic 5: Extremal Problems
36 4/20 Mon Sec 5.1: Turan's Theorem, counting triangles (through Moon-Moser), further comments on k_p(G), Lovasz-Simonovits Theorem
37 4/22 Wed Sec 5.1: Zarankiewicz Problem and related topics, Erdos-Simonovits from Erdos-Stone
38 4/24 Fri Sec 5.1: Erdos-Stone by Regularity Lemma and Embedding Lemma
39 4/27 Mon Sec 5.1: Proof of Regularity Lemma
40 4/29 Wed Sec 5.2: application of Regularity to linear Ramsey number for bounded-degree graphs, Ramsey number for paths, skipped induced Turan problems and anti-Ramsey numbers
41 5/01 Fri Sec 5.3: decomposition problems (into complete graphs, forests (mention arboricity), trees, linear forests)
42 5/04 Mon Sec 5.3-4: Lovasz path/cycle decomposition, intersection number, boxicity
43 5/06 Wed Sec 5.4: interval number, total interval number, visibility number