Basics of Ramsey Theory serves as a gentle introduction to Ramsey theory for students interested in becoming familiar with a dynamic segment of contemporary mathematics that combines ideas from number theory and combinatorics. The core of the of the book consists of discussions and proofs of the results now universally known as Ramsey’s theorem, van der Waerden’s theorem, Schur’s theorem, Rado’s theorem, the Hales–Jewett theorem, and the Happy End Problem of Erdős and Szekeres. The aim is to present these in a manner that will be challenging but enjoyable, and broadly accessible to anyone with a genuine interest in mathematics.
Features
- Suitable for any undergraduate student who has successfully completed the standard calculus sequence of courses and a standard first (or second) year linear algebra course
- Filled with visual proofs of fundamental theorems
- Contains numerous exercises (with their solutions) accessible to undergraduate students
- Serves as both a textbook or as a supplementary text in an elective course in combinatorics and aimed at a diverse group of students interested in mathematics
Author(s): Veselin Jungić
Publisher: CRC Press/Chapman & Hall
Year: 2023
Language: English
Pages: 237
City: Boca Raton
Cover
Half Title
Title Page
Copyright Page
Dedication
Contents
Foreword
Preface
Symbols
CHAPTER 1: Introduction: Pioneers and Trailblazers
1.2. PAUL ERDŐS
1.2.1. Who Was Paul Erdős?
1.2.2. Erdős’s Work: Two Examples
1.2.2.1. Happy End Problem
1.2.2.2. Erdős–Turán Conjecture
1.3. FRANK PLUMPTON RAMSEY
1.3.1. Who Was Frank Ramsey?
1.3.2. Ramsey’s Work: Two Examples
1.3.2.1. Foundations of Mathematics
1.3.2.2. Ramsey’s Theorem
1.4. RAMSEY THEORY
CHAPTER 2: Ramsey’s Theorem
2.1. THE PIGEONHOLE PRINCIPLE
2.2. ACQUAINTANCES AND STRANGERS
2.3. RAMSEY’S THEOREM FOR GRAPHS
2.4. RAMSEY’S THEOREM: AN INFINITE CASE
2.5. RAMSEY’S THEOREM: GENERAL CASE
2.6. EXERCISES
CHAPTER 3: van der Waerden’s Theorem
3.1. BARTEL VAN DER WAERDEN
3.1.1. Who Was Bartel Leendert van der Waerden?
3.1.2. van der Waerden’s Work: Two Examples
3.1.2.1. History of Mathematics
3.1.2.2. van der Waerden’s Theorem
3.2. VAN DER WAERDEN’S THEOREM: THREE-TERM ARITHMETIC PROGRESSIONS
3.2.1. Colour-focused Arithmetic Progressions
3.2.2. van der Waerden’s Theorem for Three-term Arithmetic Progressions
3.3. PROOF OF VAN DER WAERDEN’S THEOREM
3.4. VAN DER WAERDEN’S THEOREM: HOW FAR AND WHERE?
3.4.1. Bounds for van der Waerden Numbers
3.4.2. Density of Sets and Arithmetic Progressions
3.5. VAN DER WAERDEN’S THEOREM: SOME RELATED QUESTIONS
3.5.1. Mixed van der Waerden Numbers
3.5.2. Canonical Form of van der Waerden’s Theorem
3.5.3. Polynomial van der Waerden’s Theorem
3.6. EXERCISES
CHAPTER 4: Schur’s Theorem and Rado’s Theorem
4.1. ISSAI SCHUR
4.1.1. Who Was Issai Schur?
4.1.2. Schur’s Work: Two Examples
4.1.2.1. Schur Complement
4.1.2.2. Schur and Ramsey Theory
4.2. SCHUR’S THEOREM
4.3. RICHARD RADO
4.3.1. Who Was Richard Rado?
4.3.2. Rado’s Work: Two Examples
4.3.2.1. An Application of Ramsey’s Theorem
4.3.2.2. Rado’s Arrow Notation
4.4. RADO’S THEOREM
4.5. EXERCISES
CHAPTER 5: The Hales–Jewett Theorem
5.1. COMBINATORIAL LINES
5.2. GENERALIZED TIC-TAC-TOE GAME
5.3. THE HALES–JEWETT THEOREM
5.4. EXERCISES
CHAPTER 6: Happy End Problem
6.1. THE HAPPY END PROBLEM: TRIANGLES, QUADRILATERALS, AND PENTAGONS
6.2. THE HAPPY END PROBLEM: GENERAL CASE
6.2.1. Proof Via Ramsey’s Theorem
6.2.2. Proof Via Theorem on Cups and Caps
6.3. ERDŐS–SZEKERES’ UPPER AND LOWER BOUNDS
6.3.1. An Upper Bound
6.3.2. A Lower Bound
6.4. PROGRESS ON THE CONJECTURE OF ERDŐS AND SZEKERES
6.5. EXERCISES
CHAPTER 7: Solutions
7.1. CHAPTER 2: RAMSEY’S THEOREM
7.2. CHAPTER 3: VAN DER WAERDEN’S THEOREM
7.3. CHAPTER 4: SCHUR’S THEOREM AND RADO’S THEOREM
7.4. CHAPTER 5: THE HALES–JEWETT THEOREM
7.5. CHAPTER 6: HAPPY END PROBLEM
Bibliography
Index
