Fundamentals of Ramsey Theory

Aaron Robertson

• Publisher: Chapman and Hall/CRC
• Year: 2021
• ISBN:
  9780429775901
• Edition: 1
• Topic: Matemáticas
• Subtopic: Matemáticas general

Ramsey theory is a fascinating topic. The author shares his view of the topic in this contemporary overview of Ramsey theory. He presents from several points of view, adding intuition and detailed proofs, in an accessible manner unique among most books on the topic. This book covers all of the main results in Ramsey theory along with results that have not appeared in a book before.

The presentation is comprehensive and reader friendly. The book covers integer, graph, and Euclidean Ramsey theory with many proofs being combinatorial in nature. The author motivates topics and discussion, rather than just a list of theorems and proofs. In order to engage the reader, each chapter has a section of exercises.

This up-to-date book introduces the field of Ramsey theory from several different viewpoints so that the reader can decide which flavor of Ramsey theory best suits them.

Additionally, the book offers:

• A chapter providing different approaches to Ramsey theory, e.g., using topological dynamics, ergodic systems, and algebra in the Stone-?ech compactification of the integers.

• 
  
  

• A chapter on the probabilistic method since it is quite central to Ramsey-type numbers.

• 
  
  

• A unique chapter presenting some applications of Ramsey theory.

• 
  
  

• Exercises in every chapter

The intended audience consists of students and mathematicians desiring to learn about Ramsey theory. An undergraduate degree in mathematics (or its equivalent for advanced undergraduates) and a combinatorics course is assumed.

TABLE OF CONENTS

Preface

List of Figures

List of Tables

Symbols

1. Introduction

2. Integer Ramsey Theory

3. Graph Ramsey Theory

4. Euclidean Ramsey Theory

5. Other Approaches to Ramsey Theory

6. The Probabilistic Method

7. Applications

Bibliography

Index

Biography

Aaron Robertson received his Ph.D. in mathematics from Temple University under the guidance of his advisor Doron Zeilberger. Upon finishing his Ph.D. he started at Colgate University in upstate New York where he is currently Professor of Mathematics. He also serves as Associate Managing editor of the journal Integers. After a brief detour into the world of permutation patterns, he has focused most of his research on Ramsey theory.

1

Introduction

There is a light that never goes out.

–Morrissey

Unbreakable, inevitable, assured, inescapable: choose whichever synonym you prefer. Ramsey theory is the study of properties that must occur for sufficiently large structures. We can try to break the structure through partitioning, but a Ramsey property will persist.

1.1 What is Ramsey Theory?

Consider positive integer solutions to $x+y=z$. Of course, $1+1=2$ and $2+3=5$ work if we allow all positive integers. So, let's try to break this by splitting the positive integers into two parts. In Ramsey theory, we typically use colors to describe the partitions, so we will have, say, red integers and blue integers.

Must we still have a solution to $x+y=z$ if we now require the integers to be in the same partition, i.e., the same color? Let's see if we can avoid the property of one part of the partition having a solution to $x+y=z$. First, 1 and 2 must be different colors (since $1+1=2$) and, consequently, 4 must be the same color as 1 (since $2+2=4$). Let's say that 1 and 4 are red and 2 is blue. Since $1+4=5$, we see that 5 must also be blue, and, consequently, 3 must be red (since $2+3=5$). But now 1,3, and 4 are all red, so the Ramsey property persists.

Ramsey properties also exist on graphs. For example, if we take $n\ge 3$ vertices and connect every pair of vertices with an edge, we clearly have a triangle with all edges in the same partition. Can we partition the edges in such a way so that we no longer have a triangle with all edges in the same partition? The answer is no, provided we have at least 6 vertices. To see this, isolate one vertex, say X. Using the colors red and blue, since X is connected to at least 5 other vertices, we see that one of the colors must occur on at least 3 of the edges. Let X be connected to each of vertices A, B, and C with a blue edge. If any...