MATH 7016 - Combinatorics
Spring 2009 - Tuesday/Thursday 16:30-18:00
Home Assignments
Topics covered
-
Lecture 1:
Upper bound for R(t,t). Upper bound for R(s,t). Lower bound for R(t,t). Applications of Hypergraph Ramsey to finding convex sets
using 3-graphs and 4-graphs.
-
Lecture 2:
Hypergraph Ramsey with k-colors reduces to 2 colors. 2-color Hypergraph Ramsey.
Upper and lower bound for Ramsey numbers of triangles and k colors.
Schur's
theorem.
-
Lecture 3:
Goodman's theorem. Graph Ramsey numbers of Clique vs Tree. Ramsey number of clique/induced-star/induced-path in connected graphs.
Induced Ramsey Theorem (without proof).
-
Lecture 4:
Two proofs of the Erdos Szekeres lemma. Some exact Ramsey numbers. van-der Waerdan's Theorem for 2-colors/3-term AP.
-
Lecture 5:
Proof of van-der Waerdan's Theorem.
-
Lecture 6:
Ramsey version of Szemeredi's Affine Cube Lemma.
Density version of Affine Cube Lemma.
Szemeredi's theorem (without proof).
-
Lecture 7:
Behrend's construction. Lower bound for density version of replete Affine d-Cubes.
Roth's Theorem using Triangle Removal Lemma.
-
Lecture 8:
Density version of homogenous equations with coefficients summing to 0.
Deducing Szemeredi's Theorem from the Hypergraph Removal Lemma (without
proof). Solution of home assignment 1.
-
Lecture 9:
High girth and high chromatic number. Erdos's local-vs-global coloring Theorem.
-
Lecture 10:
Local-vs-global 2-colorability in dense graphs.
-
Lecture 11:
Local-vs-global 3-colorability in dense graphs. Solution of home
assignments.
-
Lecture 12:
Choice number of planar graphs (Thomassen's Theorem). Orientations,
kernels, and choosability. Choice number of planar bipartite graphs.
-
Lecture 13:
Choice number of degenerate bipartite graphs. Examples of planar graphs
with high choice number. The chromatic index of bipartite graphs (Konig's
Theorem).
-
Lecture 14:
Stable Matchings and the Gale-Shapley Theorem. The list chromatic index of
bipartite graphs (Dinitz Problem). The list coloring conjecture and Kahn's
Theorem (without proof). Long cycles/paths in color-critical graphs.
-
Lecture 15:
Konig's Infinity Lemma. The de-Bruijn-Erdos Theorem. Solution of home
assignments.
-
Lecture 16:
Perfect graphs. Kovari-Sos-Turan Theorem.
-
Lecture 17:
Application of the KST Theorem to unit distance problem. Algebraic proof
of the Weak
Perfect Graph Theorem (Lovasz Theorem).
-
Lecture 18:
Erdos-Stone Theorem via the hypergraph version of the KST-Theorem.
Sperner's Theorem using
Hall and via LYM Inequality. The Littlewood-Offord Problem.
-
Lecture 19:
Odd-town Theorem. Even-town Theorem. 2-distance sets.
-
Lecture 20:
Nagy's Ramsey construction. Restricted intersections,
Frankl-Wilson Theorem. Modular restricted intersections,
Deza-Frankl-Singhi Theorem. Frankl-Wilson Ramsey construction. Lindstrom's
Theorem.
-
Lecture 21:
Missing intersection Theorem. Chromatic number of R^n.
-
Lecture 22:
Kahn-Kalai counter example to Borsuk's conjecture. Bollobas's Theorem.
-
Lecture 23:
Home assignments. Intersection theorem for uniform sets (Blokhuis trick).
Graham-Pollack Theorem.
-
Lecture 24:
Dual Fischer Inequality. Partitioning K_n into disjoint cliques. Number of
lines determined by non-collinear points. Theorem's of Radon, Helly and
Caratheodory.
-
Lecture 25:
Decomposing K_10 into 3 Peterson graphs. Algebraic proof of Bollobas's
Theorem. Application to Helly-type property of hypergraph vertex-cover.
-
Lecture 26:
Hoffman-Singleton Theorem. Bondy's Theorem.
-
Lecture 27:
Dehn's Theorem (Hilbert's third problem) and the Bolyai-Gerwien Theorem.