Math 264C, Combinatorics, Ramsey Theory, Spring 2019

Coordinator: Andrew Suk
Office: APM 6210
E-mail: asuk [@] ucsd [dot] edu
Time and Place:, APM 2404, Wed 12:00-12:50pm

Description: This course will cover several important results in Ramsey Theory. Ramsey theory refers to a large body of deep results in mathematics whose underlying philosophy is that "Every sufficiently large system contains a large well organized subsystem." We will cover some of the most recent results in the area for graphs and hypergraphs with applications in number theory and discrete geometry.

Grades: Will be based on class participation and presentation.


4/1/2019: Graph Ramsey numbers. Diagonal and off-diagonal Ramsey numbers.
4/3/2019: The Erdos-Szekeres monotone subsequence theorem and cups caps theorem. r(P_m,K_n). Reference.
4/5/2019: Hypergraph Ramsey numbers, r_3(n,n).
4/8/2019: r(3,n) and cycle-complete Ramsey numbers.
4/10/2019: The Erdos-Rado upper bound argument, lower bound for r_3(4,n).
4/12/2019: A better lower bound for r_3(4,n). Reference.
4/15/2019: The stepping up lemma: Lower bounds for r_3(n,n,n) and r_3(n,n,n,n).
4/17/2019: More on the stepping lemma: Lower bounds for r_k(s,n).
4/19/2019: Monotone paths versus cliques. Reference.
4/22/2019: The Erdos-Hajnal conjecture. Reference.
4/24/2019: The Erdos-Hajnal theorem on graphs with a forbidden induced subgraph.
4/26/2019: VC-dimension, Sauer-Shelah.
4/29/2019: Haussler's packing lemma, unit distance graph for a set system.
5/1/2019: Finish the proof of Haussler's packing lemma.
5/3/2019: Fisher's inequality, L-intersecting families.
5/6/2019: Very explicit constructions of Ramsey graphs by Frankl and Wilson.
5/8/2019: Schur numbers and multicolor Ramsey numbers.
5/10/2019: Lower bounds for Schur numbers: Lemmas of Abbott-Moser and Fredricksen-Sweet. Generalized Schur numbers and open problems.
5/13/2019: Counting monochromatic Schur Triples.
5/15/2019: Finish Datskovsky's proof on the number of monochromatic Schur triples.
5/17/2019: Van der Waerden's theorem.
5/20/2019: Regularity lemma, removal lemma, and Roth's theorem.
5/22/2019: A Ramsey theorem for affine subspaces (Sam McGuire).
5/24/2019: Shannon capacities of graphs with bounded independence number (Jacob Naranjo). A Ramsey-type theorem on the max-cut value of d-regular graphs (Rex Lei).
5/29/2019: Bounding the VC-dimension of a hypergraph based on degeneracy (Renee Mirka). Ramsey numbers for bounded degree graphs (Sayok Chakravarty).
5/31/2019: Hypergraph Ramsey numbers: triangles vs cliques (Jiaxi Nie). Hales Jewett Theorem (Ryan Schneider).
6/3/2019: The Hadwiger Nelson problem (Nice Sieger). (n,k,L)-set systems and the Deza-Erdos-Frankl upper bound (Jason O'neill).
6/5/2019: Epsilon-nets (Max Hopkins).
6/7/2019: Ramsey numbers for cycles vs wheels (An Ran Chen).


Class presentation: Schedule is here. This is a 25 min presentation on a theorem or exercise in Ramsey theory. E-mail me at least 1 week before the presentation for topic approval.