Home Research Teaching Other

Fall 2009: Ramsey Theory 21-801 Class information Class meetings: MW 12:30pm - 1:50pm, Porter Hall A21A Office hours: Th 1:00pm - 3:00pm or by appointment Syllabus: Resources Graph Theory by Reinhard Diestel Ramsey Theory Applications by Vera Rosta Arithmetic Ramsey Theory by Terry Tao Course outline (to be updated during the term) Date Topic Remarks 8/24 Ramsey theorems for pairs Graham & Rödl Radziszowski 8/26 Lower bounds on Ramsey numbers + Ramsey theorems for k-subsets + The Erdős and Szekeres paper Alon & Spencer Erdős & Szekeres 8/31 Infinite Ramsey theorems + Compactness principle see also Section 8.1 in Diestel 9/2 Linear Ramsey numbers Chvatál et al. 9/7 Labor Day - no classes 9/9 Off-diagonal Ramsey numbers, e.g., R(3,n) Alon & Spencer Spencer 9/14 NP-hardness of determining the Ramsey numbers Burr 9/16 Van der Waerden's theorem 9/21 Van der Waerden's theorem (contd.) + The Ackermann hierarchy 9/23 The Hales and Jewett theorem + Gallai's theorem + The Shelah proof 9/28 The Shelah proof of the Hales and Jewett theorem (contd.) 9/30 Roth's theorem (the removal lemma approach) see Theorem 1.1 in Gowers 10/5 Roth's theorem (the Fourier analytic approach) Fourier Roth 10/7 Roth's theorem and the Fourier analytic approach (contd.) + Behrend's theorem Behrend 10/12 Schur's theorem + Fermat's last theorem in Zp (combinatorial and Fourier analytic approaches) Schur 10/14 Monochromatic Schur triples + Rado's theorem Schoen 10/19 Rado's theorem (contd.) 10/21 The Folkman-Rado-Sanders theorem Erdős & Spencer 10/26 Bipartite Ramsey theorems 10/28 Bipartite Ramsey theorems (contd.) See Sections 1.4 and 2 11/2 Vertex Ramsey-type problems 11/4 Vertex Ramsey-type problems (contd.) 11/9 Constructive lower bounds for diagonal Ramsey numbers + Chromatic number of the unit-distance graph Frankl & Wilson 11/11 The partite construction of Nešetřil and Rödl + Ramsey graphs for triangles with no K4 Frankl & Rödl 11/16 Euclidean Ramsey theory Frankl & Rödl 11/18 Vertex-coloring edge-weightings 11/23 The size Ramsey number Erdős et al. Beck 11/25 Thanksgiving break - no classes