MATH 581 / CS 572

EXTREMAL GRAPH THEORY, Spring 2011

Summary of Lectures

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

Topic 1: Trees and Distance
Lec1 1/19 Wed Sec 1.1: spanning trees with many leaves (min degree 3, general min degree)
Lec2 1/21 Fri Sec 1.1: Huffman coding, Shannon bound, optimal alphabetic trees (dynamic programming, Hu-Tucker algorithm), intro to eccentricity/radius/diameter (Harary-Norman)
Lec3 1/24 Mon Sec 1.2: Moore bound, Hoffman-Singleton graph, small graphs with fixed order/diameter/maxdegree
Lec4 1/26 Wed Sec 1.2: oriented diameter (construction, Chvatal-Thomassen bound, brief sketch of improvement for diameter 2)
Lec5 1/28 Fri Sec 1.2: diameter vs. average distance, diameter vulnerability, independence bounds on connected domination and average distance
Lec6 1/31 Mon Sec 1.3: squashed-cube dimension (examples, eigenvalue bound, Winkler's Theorem)
x 2/02 Wed: Snow Day
Lec7 2/04 Fri Sec 1.3: bandwidth: density bound (caterpillars), boundary bound (grids), increase under edge addition, Sperner's Lemma (triangular grid), mention of edge bandwidth (B'(G)>B(G))

Topic 2: Matching and Independence
Lec8 2/07 Mon Sec 2.1: Hall's Theorem with lower bound on #matchings, rancher/farmer problem (Marcus-Ree Theorem), review of classical applications (Marriage Theorem, Birkhoff-von Neuman Theorem, Ore's Defect Formula, Konig-Egervary Theorem), Tutte 1-factor Theorem via Berge-Tutte Formula
Lec9 2/09 Wed Sec 2.1: Gallai-Edmonds Structure Theorem, state Plesnik's Theorem (review), Lovasz/Zaks #matchings in k-connected graphs, smallest matching number in k-regular graphs
Lec10 2/11 Fri Sec 2.2: augmenting paths, fast bipartite matching, Edmonds' Blossom algorithm, intro to weighted matching
Lec11 2/14 Mon Sec 2.2: weighted matching, on-line ski rental, on-line bipartite matching (mostly overview)
Lec12 2/16 Wed Sec 2.3: Tutte's f-Factor Theorem (reduction to 1-factors, necessity and sufficiency)
Lec13 2/18 Fri Sec 2.3: Parity Lemma, Erdos-Gallai conditions, regular factors in regular graphs (Hanson-Loten-Toft), skipped toughness, briefly mentioned g,f-factor problem and complexity of testing
Lec14 2/21 Mon Sec 2.4: maximum stable sets (Berge characterization), greedy algorithms, Caro-Wei Theorem, critical edges, Bondy bound on vertex cover number.
Lec15 2/23 Wed Sec 2.4: independence ratio in cubic triangle-free graphs (state results), domination number (Arnautov-Payan bound, Gallai edge bound for fixed domination number
Lec16 2/25 Fri Sec 2.4: odd dominating sets, independent domination in claw-free graphs, kernels in digraphs, introduction to generalized coloring (families Ok, Sk, Dk, Ck)

Topic 3: Coloring
Lec17 2/28 Mon Sec 3.1: k-greedy coloring, Matula generalization of Brooks, Lovász partition into classes with bounded maximum degree
Lec18 3/02 Wed Sec 3.1: acyclic coloring (upper bound algorithm for maxdegree 3, general maxdegree, Alon-McDiarmid-Reed probabilistic lower bound), star coloring (equivalence with in-coloring)
Lec19 3/04 Fri Sec 3.1: star coloring (quadratic maxdegree upper bound, mention upper bound via acyclic coloring, acyclic and star coloring for planar graphs, A-C-K-K-R inductive construction), nonrepetitive coloring (sketch bound of 4 for trees), start injective coloring (degree upper bound)
Lec20 3/07 Mon Sec 3.2: (finish injective coloring for Mad(G)≤36/13), Descartes girth 6 & large chromatic number, construction for large chromatic number & girth
Lec21 3/09 Wed Sec 3.2: Color-critical: generalized Hajos construction, minimum excess degree (Dirac by statement, prove Gallai's bound)
Lec22 3/11 Fri Sec 3.2: broom-free graphs weakly chi-bounded, Dirac K_4-subdivision, Hajos and Hadwiger conjectures, min degree for F-subdivision
Lec23 3/14 Mon Sec 3.3: review of elementary coloring results (Konig, Vizing-Gupta, Anderson-Goldberg), (skipped Vizing Adjacency Lemma), Erdos-Faber-Lovasz reduction, Chang-Lawler coloring of linear hypergraphs

Topic 4: Refined Coloring Models & Perfection
Lec24 3/16 Wed Sec 3.3: parity edge-coloring
Lec25 3/18 Fri Sec 3.3: interval edge-coloring (proof of elementary results, statement of others), skipped proper weighting
Lec26 3/28 Mon Sec 3.4: List coloring (bipartite choosability vs. 2-coloring hypergraphs, Alon's lower bound from average degree).
Lec27 3/30 Wed Sec 3.4: List coloring conjecture, f-choosability and kernels, Galvin's List Color Theorem, Borodin-Kostochka-Woodall list version of Shannon
Lec28 4/01 Fri Sec 3.4: 3-choosability of planar bipartite graphs, Alon-Tarsi Theorem (3-choosability of squares of cycles),
Lec29 4/04 Mon Sec 3.4: Combinatorial Nullstellensatz and applications (skipped (1,2)-choosability of even trees)
Lec30 4/06 Wed Sec 3.5: intro to circular coloring, properties of circular and (k,d)-colorings, condition for χc
Lec31 4/08 Fri Sec 3.5: Goddyn-Tarsi-Zhang generalization of Minty to circular coloring upper bounds on χc by Steffen-Zhu and Zhu (generalizing Tuza)
Lec32 4/11 Mon Sec 4.1: classical examples of perfect graphs, comparability, chordal, The Perfect Graph Theorem
Lec33 4/13 Wed Sec 4.1: perfectly orderable graphs, star-cutset lemma, comments on Meyniel graphs and weakly chordal graphs
Lec34 4/15 Fri Sec 4.2-3: comments on partitionable graphs and Strong Perfect Graph Theorem, chordal graphs (intersection representation)
Lec35 4/18 Mon Sec 4.3: comments on split, strongly chordal/bichordal graphs, characterizations of interval graphs (skipped unit interval), comments on threshold and parity graphs

Topic 5: Extremal Problems
Lec36 4/20 Wed Sec 5.1: Turan's Theorem, counting triangles (through Moon-Moser), further comments on kp(G), state Lovasz-Simonovits Theorem
Lec37 4/22 Fri Sec 5.1: saturation numbers, Erdos-Simonovits from Erdos-Stone, Erdos-Stone by Nikiforov
Lec38 4/25 Mon Sec 5.1: extremal problems for hypergraphs, covering numbers, Chvatal-McDiarmid theorem.
Lec39 4/27 Wed Sec 5.2: graph Ramsey numbers (tree/clique, mK3, path/path, etc.)
Lec40 4/29 Fri Sec 5.2: multicolor bipartite Ramsey for P4 (mentioned C4), parameter Ramsey numbers, chromatic Ramsey number, (skipped mention of linear Ramsey for bounded degree, anti-Ramsey numbers)
Lec41 5/02 Mon Sec 5.3: decomposition problems (into complete graphs, forests (mention arboricity), trees, linear forests, fractional arboricity)
Lec42 5/04 Wed Sec 5.3-4: Lovasz path/cycle decomposition, intersection number, boxicity
Lec43 5/05 Thu Sec 5.4: boxicity, interval number, brief mention of total interval number, skipped visibility number !-->