Computational and theoretical aspects of Ramsey theory

Timetable

Tentative Timetable. Discussions regarding SAT-solvers and computational methods will be mixed in depending on student interest.

Week 1: What is Ramsey Theory, Ramsey's Theorem, and Ramsey Numbers

Week 2: Schur's Theorem, Van der Waerden's Theorem, Schur numbers and Van der Waerden Numbers

Week 3:  The compactness principle, Roth's Theorem, Szemeredi's Theorem

Week 4: Finite sum's Theorem, Deuber's Theorem, and Rado's Theorem

Week 5: The Hales-Jewett Theorem

Week 6: The canonical Ramsey's Theorem and the canonical Van der Waerden Theorem

Week 7: The polynomial van der Waerden Theorem and polynomial Szemeredi Theorem.

The rest of the semester will be reserved for topics of interest to the students. This may include computational methods used to calculate Ramsey numbers, which could also happen during the first 7 weeks instead of after, or it may include more theoretical topics such as Hindman's Theorem and infinite Ramsey Theory, Ramsey Theory mixing addition and multiplication, central sets, ultrafilters, and connections to dynamics.

Module aim (aims)

To introduce students to the basics of Ramsey theory. Students will have the choice of traditional proof based homework exercises or programming exercises based on whether they are more interested in computer science or pure math. The goal for students who are interested in computer science would be to compute some new Ramsey numbers using SAT-solvers and parallel computing, potentially resulting in a publishable journal article. The goal for students who are interested in pure math would be to understand the open problems in modern Ramsey theory and be able to start research in the area after the course.

Pre-requisites in terms of knowledge, skills and social competences (where relevant)

A prior course in elementary combinatorics will be useful but not strictly necessary. Programming ability will be necessary if you want to do the programming exercises instead of the proof based exercises. Knowledge regarding parallel computation can be helpful for the ambitious students who want to calculate new Ramsey numbers to publish in a research article. The understanding of how to prove a mathematical statement will be necessary to do the math exercises.

Syllabus

The grade in this course will be determined by a combination of homework assignments and projects. 

Reading list

Ramsey Theory, 2nd Edition, by R. L. Graham, B. L. Rothschild, and J. H. Spencer

• ISBN-10 ‏ : ‎ 9780471500469
• ISBN-13 ‏ : ‎ 978-0471500469

Journal articles will also be given to the students throughout the course depending on the topics covered.