MATH 7016 - Combinatorics
Spring 2009 - Tuesday/Thursday 16:30-18:00
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.
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.
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).
Two proofs of the Erdos Szekeres lemma. Some exact Ramsey numbers. van-der Waerdan's Theorem for 2-colors/3-term AP.
Proof of van-der Waerdan's Theorem.
Ramsey version of Szemeredi's Affine Cube Lemma.
Density version of Affine Cube Lemma.
Szemeredi's theorem (without proof).
Behrend's construction. Lower bound for density version of replete Affine d-Cubes.
Roth's Theorem using Triangle Removal Lemma.
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.
High girth and high chromatic number. Erdos's local-vs-global coloring Theorem.
Local-vs-global 2-colorability in dense graphs.
Local-vs-global 3-colorability in dense graphs. Solution of home
Choice number of planar graphs (Thomassen's Theorem). Orientations,
kernels, and choosability. Choice number of planar bipartite graphs.
Choice number of degenerate bipartite graphs. Examples of planar graphs
with high choice number. The chromatic index of bipartite graphs (Konig's
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.
Konig's Infinity Lemma. The de-Bruijn-Erdos Theorem. Solution of home
Perfect graphs. Kovari-Sos-Turan Theorem.
Application of the KST Theorem to unit distance problem. Algebraic proof
of the Weak
Perfect Graph Theorem (Lovasz Theorem).
Erdos-Stone Theorem via the hypergraph version of the KST-Theorem.
Sperner's Theorem using
Hall and via LYM Inequality. The Littlewood-Offord Problem.
Odd-town Theorem. Even-town Theorem. 2-distance sets.
Nagy's Ramsey construction. Restricted intersections,
Frankl-Wilson Theorem. Modular restricted intersections,
Deza-Frankl-Singhi Theorem. Frankl-Wilson Ramsey construction. Lindstrom's
Missing intersection Theorem. Chromatic number of R^n.
Kahn-Kalai counter example to Borsuk's conjecture. Bollobas's Theorem.
Home assignments. Intersection theorem for uniform sets (Blokhuis trick).
Dual Fischer Inequality. Partitioning K_n into disjoint cliques. Number of
lines determined by non-collinear points. Theorem's of Radon, Helly and
Decomposing K_10 into 3 Peterson graphs. Algebraic proof of Bollobas's
Theorem. Application to Helly-type property of hypergraph vertex-cover.
Hoffman-Singleton Theorem. Bondy's Theorem.
Dehn's Theorem (Hilbert's third problem) and the Bolyai-Gerwien Theorem.