MATH 7016  Combinatorics
Spring 2009  Tuesday/Thursday 16:3018: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 3graphs and 4graphs.

Lecture 2:
Hypergraph Ramsey with kcolors reduces to 2 colors. 2color 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/inducedstar/inducedpath in connected graphs.
Induced Ramsey Theorem (without proof).

Lecture 4:
Two proofs of the Erdos Szekeres lemma. Some exact Ramsey numbers. vander Waerdan's Theorem for 2colors/3term AP.

Lecture 5:
Proof of vander 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 dCubes.
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 localvsglobal coloring Theorem.

Lecture 10:
Localvsglobal 2colorability in dense graphs.

Lecture 11:
Localvsglobal 3colorability 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 GaleShapley Theorem. The list chromatic index of
bipartite graphs (Dinitz Problem). The list coloring conjecture and Kahn's
Theorem (without proof). Long cycles/paths in colorcritical graphs.

Lecture 15:
Konig's Infinity Lemma. The deBruijnErdos Theorem. Solution of home
assignments.

Lecture 16:
Perfect graphs. KovariSosTuran Theorem.

Lecture 17:
Application of the KST Theorem to unit distance problem. Algebraic proof
of the Weak
Perfect Graph Theorem (Lovasz Theorem).

Lecture 18:
ErdosStone Theorem via the hypergraph version of the KSTTheorem.
Sperner's Theorem using
Hall and via LYM Inequality. The LittlewoodOfford Problem.

Lecture 19:
Oddtown Theorem. Eventown Theorem. 2distance sets.

Lecture 20:
Nagy's Ramsey construction. Restricted intersections,
FranklWilson Theorem. Modular restricted intersections,
DezaFranklSinghi Theorem. FranklWilson Ramsey construction. Lindstrom's
Theorem.

Lecture 21:
Missing intersection Theorem. Chromatic number of R^n.

Lecture 22:
KahnKalai counter example to Borsuk's conjecture. Bollobas's Theorem.

Lecture 23:
Home assignments. Intersection theorem for uniform sets (Blokhuis trick).
GrahamPollack Theorem.

Lecture 24:
Dual Fischer Inequality. Partitioning K_n into disjoint cliques. Number of
lines determined by noncollinear 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 Hellytype property of hypergraph vertexcover.

Lecture 26:
HoffmanSingleton Theorem. Bondy's Theorem.

Lecture 27:
Dehn's Theorem (Hilbert's third problem) and the BolyaiGerwien Theorem.