Ma 191b Sec 3: Introduction to Ramsey Theory (Winter 2015-16)

ANNOUNCEMENTS


COURSE DESCRIPTION

Ramsey Theory studies, broadly speaking, the following question: which combinatorial configurations can be found in a sufficiently large set? This course will provide an overview of this subject, starting from its roots, passing from finite and infinite Ramsey theory, and arriving to the current research on structural Ramsey theory for discrete and metric structures. The interactions with logic (ultrafilter method, nonstandard analysis) and topological dynamics (universal minimal flows) will be emphasized.


PREREQUISITES

There are no  specific prerequisites.


SCHEDULE

TR 10:30 - 11:55
151 Sloan


INSTRUCTORS

Martino Lupini
260 Sloan
626-395-4340


OFFICE HOURS

Thurday at 5pm and by appointment


POLICIES

 


TOPICS COVERED

Lecture 1: Ramsey's theorem, finite and infinite version, graph-theoretic interpretation, arrow notation, cominatorial proof (see Section 1.2 and 1.3 of Prömel's book or Section 1 of Nesetril's survey "Ramsey theory"). Coideals and ultrafilters, ultrafilter quantifiers, Fubini product of ultrafilters, ultrafilter proof of Ramsey's theorem (see  Section 1.1 and 1.2 of Todorcevic's book).

Lecture 2: The Erdos-Szekeres theorem (see Section 1.3 of Prömel's book). The Ramsey canonization theorem and the Erdos-Rado canonization theorem (see the notes of Jan 7th below, or Section 1.2 of Todorcevic's book, or Section 1.4 of Prömel's book).

Lecture 3: Statement of the van der Waerden theorm (see Section 2.3 of Prömel's book). Topology on the space of ultrafilters and Stone-Cech compactification of a discrete space (see Sections 3.1, 3.2, 3.3 of "Algebra in the Stone-Cech compactification"). Sum of ultrafilters on N and semigroup compactifications  (see Section 4.1 of "Algebra in the Stone-Cech compactification").

Lecture 4:  Fundamental results from the theory of compact right topological semigroup. The Ellis-Numakura theorem on existence of idempotents. Minimal left ideals and minimal idempotents. Characterization of idempotents. The smallest ideal. (See Chapter 3 of "Algebra in the Stone-Cech compactification".)

Lecture 5: Ultrafilter proof of van der Waerden's theorem (see Theorem 14.1 in "Algebra in the Stone-Cech compactification"). Thick, syndetic, and piecewise syndetic sets, and statement of the characterization of the closure of the smallest ideal of the space of ultrafilters over N (see Section 4,4 in "Algebra in the Stone-Chech compactification"). Fundamental notions about dynamical systems. Minimal dynamical system. (See Lecture 2 of Tao's blog.) Existence and uniqueness of the universal minimal dynamical system (see Section 19.1 in "Algebra in the Stone-Cech compactification").

Lecture 6: Recurrent and uniformly recurrent points, statement of the characterization of uniformly recurrent points, and Birkhoff's single recurrence theorem (see Section 19.1 in "Algebra in the Stone-Cech compactification" or Lecture 3 of Tao's blog). Statement of Birkhoff's multiple recurrence theorem (MBR) (see Section 5 of the Introduction to "Recurrence in ergodic theory and combinatorial number theory"). Proof that MBR implies the multidimensional van der Waerden theorem (see Section 3 of Chapter 2 of "Recurrence in ergodic theory and combinatorial number theory").

Lecture 7: Uniformly recurrent points in the space of ultrafilters over N (see Theorem 4.39 of "Algebra in the Stone-Cech compactification" or Lecture 3 of Tao's blog).  Proof of Birkhoff's multiple recurrence theorem, Part I (see Section 1 and 2 of Chapter 2 of "Recurrence in ergodic theory and combinatorial number theory").

Lecture 8: Proof of Birkhoff's multiple recurrence theorem, Part II (see Section 1 and 2 of Chapter 2 of "Recurrence in ergodic theory and combinatorial number theory"). Ultrafilter proof of Hindman's theorem (see Section 5.2 of "Algebra in the Stone-Cech compactification")

Lecture 9: Introduction to nonstandard methods. The transfer property. Hypernatural numbers. Hyperreal numbers. The standard part. Nonstandard characterization of limit points of a sequence. Internal sets. Overspill and underspill. Nonstandard characterization of thick sets, syndetic sets, and piecewise syndetic sets. Nonstandard proof that piecewise syndetic sets form a coideal. (See  "Introduction of nonstandard methods for number theorists" pages 1-13 or "A taste of nonstandard methods in combinatorics of numbers" Sections 1,2,3)

Lecture 10: Furstenberg theorem on A-A when A has positive Banach density, and Jin's theorem on A-B when A,B have positive Banach density (see Theorem 3.3 of "Embeddability properties of difference sets")

Lecture 11: Iterated hyperextensions (see "A taste of nonstandard methods in combinatorics of numbers", Section 4). Correspondence between ultrafilters and hypernatural numbers. (see " Hypernatural numbers as ultrafilters"). Nonstandard proof that the center of betaN is N (see Theorem 7.4 of "Hypernatural numbers as ultrafilters".) Nonstandard proof of Ramsey's theorem and of Hindman's theorem (see "A taste of nonstandard methods in combinatorics of numbers", Section 4).

Lecture 12: U-equivalence of hypernatural numbers and sequences (see  "Iterated hyper-extensions and an idempotent ultrafilter proof of Rado's Theorem"). Nonstandard proof of the theorem of Milliken and Taylor on Milliken-Taylor systems (see Theorem 3.8 in "Iterated hyper-extensions and an idempotent ultrafilter proof of Rado's Theorem"). Nonstandard proof of the Milliken-Taylor theorem (as stated in Theorem 4.1 of "Polynomial extensions of the Milliken-Taylor theorem"). Partition regularity for systems of equations and ultrafilter characterization (see Theorem 5.7 in "Algebra in the Stone-Cech compactification").

Lecture 13: Nonstandard characterization of partition regularity (see "Iterated hyper-extensions and an idempotent ultrafilter proof of Rado's Theorem"). Rado's theorem on partition regularity of systems of linear equations (see Section 2.5.1 in Promel's book). Sketch of the nonstandard proof in the case of a single linear equation with sum of the coefficients equal to 0 (see "Iterated hyper-extensions and an idempotent ultrafilter proof of Rado's Theorem").

Lecture 14: Gower's theorem on FIN_k (see Section 2.3 of "Introduction to Ramsey Spaces")

Lecture 15: Discussion o Gower's theorem and oscilation-stability of c_0 (see Section 2.4 of "Introduction to Ramsey Spaces"). The Hales-Jewett theorem (see Section 2.5 of "Introduction to Ramsey Spaces").

Lecture 16: Deuber's theorem on (m,p,c)-sets from the Hales-Jewett theorem (Section 4.2.3 of Prömel's book). Rado's theorem on partition regularity of systems of linear equations from Deber's theorem (Section 2.5.2 of  Prömel's book).

Lecture 17: Trees, product of trees, and dense subsets. The somewhere dense, highly dense, and strong subtree formulations of the Halpern-Läuchli theorem (Section 3.1 of "Introduction to Ramsey Spaces")

Lecture 18: Main ideas of the proof of the strong subtree version of the Halpern-Läuchli  theorem (see "A proof of Halpern–Läuchli partition theorem")

Lecture 19: Statement of the Graham-Rothschild theorem and applications: Ramsey's theorem, Rado-Folkman-Sanders theorem, dual Ramsey theorem, Boolean lattices (see Chapter 3 and Chapter 5 of Prömel's book). Introduction to structural Ramsey theory.


TEXTBOOKS

There is no official textbook. We list below some recommended reading containing most of the topics covered.

H.J. Prömel, Ramsey theory for discrete structures, 2013

S. Todorcevic, Introduction to Ramsey spaces, 2010

J. Nesetril, Ramsey theory, from the Handbook of Combinatorics (Volume 2), 1995

H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, 1981

N. Hindman and D. Strauss, Algebra in the Stone-Cech compactification, 1998 (second edition 2012)

T. Tao, course notes for MATH 254A Topics in ergodic theory, available at  https://terrytao.wordpress.com/category/teaching/254a-ergodic-theory/

M. Di Nasso, Iterated hyper-extensions and an idempotent ultrafilter proof of Rado's Theorem, 2015

M. Di Nasso, Embeddability properties of difference sets, Integers, 2014

M. Di Nasso, A taste of nonstandard methods in combinatorics of numbers. In "Geometry, structure and randomness in combinatorics", Pisa, 2015. Available at http://arxiv.org/abs/1312.5059

M. Di Nasso, Hypernatural numbers as ultrafilters. Available at http://arxiv.org/abs/1501.05755

R. Jin, Introduction of nonstandard methods for number theorists, 2008. Available at http://www.integers-ejcnt.org/vol8-2.html

V. Bergelson, N. Hindman, K. Williams,  Polynomial extensions of the Milliken-Taylor Theorem

S. Argyros, V. Felouzis, V. Kanellopoulos, A proof of Halpern–Läuchli partition theorem


LECTURE NOTES

Date Description
January 7, 2016 The Ramsey and Erdos-Rado canonization theorems
   
   

HOMEWORK

Due Date Homework Solutions
January 19th Assignment 1  
January 26th Assignment 2  
February 2nd Assignment 3  
February 16th Assignment 4  
February 23rd Assignment 5  
March 1st Assignment 6  
     
     

EXAMS

There will be no final exam. The final grade will be based upon 6 written assignments.


READING