Ramsey Theory

Ramsey theory is a relatively 'œnew,' approximately 100 year-old direction of fascinating mathematical thought that touches on many classic fields of mathematics such as combinatorics, number theory, geometry, ergodic theory, topology, combinatorial geometry, set theory, and measure theory. Ramsey theory possesses its own unifying ideas, and some of its results are among the most beautiful theorems of mathematics. The underlying theme of Ramsey theory can be formulated as: any finite coloring of a large enough system contains a monochromatic subsystem of higher degree of organization than the system itself, or as T.S. Motzkin famously put it, absolute disorder is impossible.Ramsey Theory: Yesterday, Today, and Tomorrow explores the theory's history, recent developments, and some promising future directions through invited surveys written by prominent researchers in the field. The first three surveys provide historical background on the subject; the last three address Euclidean Ramsey theory and related coloring problems. In addition, open problems posed throughout the volume and in the concluding open problem chapter will appeal to graduate students and mathematicians alike.

What This Book is About and How it Came into Being	p. vii
Ramsey Theory Before Ramsey, Prehistory and Early History: An Essay in 13 Parts	p. 1
Overture	p. 1
David Hilbert's 1892 Cube Lemma	p. 2
The Issai Schur 1916 Theorem	p. 3
The Baudet-Schur-Van der Waerden 1927 Theorem	p. 7
The Generalized 1928 Schur Theorem	p. 8
The Frank Plumpton Ramsey Principle	p. 9
The Paul, Gjörgy, and Esther Happy End Problem	p. 11
Richard Rado's Regularity	p. 14
Density and Arithmetic Progressions	p. 17
The Tibor Gallai Theorem	p. 22
De Bruijn-Erdos's 1951 Compactness Theorem	p. 23
Khinchin's Small Book of Big Impact	p. 23
Long Live the Young Theory!	p. 24
References	p. 25
Eighty Years of Ramsey R(3, k) à and Counting!	p. 27
Basics	p. 27
George, Esther, Paul	p. 28
Erdos Magic	p. 29
An Erdos Gem	p. 30
Upper Bounds	p. 31
The Lovász Local Lemma	p. 33
Random Greedy Triangle-Free	p. 34
R(3, k) Resolved!	p. 35
Random Greedy Triangle-Free Redux	p. 36
Epilogue	p. 38
References	p. 38
Ramsey Numbers Involving Cycles	p. 41
Scope and Notation	p. 41
Two-Color Numbers Involving Cycles	p. 42
Cycles	p. 43
Cycles Versus Complete Graphs	p. 44
Cycles Versus Wheels	p. 46
Cycles Versus Books	p. 47
Cycles Versus Other Graphs	p. 49
Multicolor Numbers for Cycles	p. 50
Three Colors	p. 50
More Colors	p. 53
Cycles Versus Other Graphs	p. 54
Hypergraph Numbers for Cycles	p. 55
References	p. 56
On the Function of Erdos and Rogers	p. 63
Introduction	p. 63
The Most Restrictive Case	p. 64
Proof of f_s,s+1(n)≤0(n^{1-1/0(s⁴log s)})[1]	p. 65
Proof of ¿(n^½)≤f_s,s+1(n) for s≥2[2]	p. 67
Proof of f_s,s+1(n) ≤0(n^2/3) for s≥2 [4]	p. 67
General Bounds	p. 69
Proof of ¿(n^a_k(s))≤f_s,s+k(n) [14, 15]	p. 71
Sketch of the Proof of f_s,s+k(n)≤0(n^{((k+1)/(2k+1))+¿}) for s≥s₀ = s₀(¿, k) [4]	p. 73
Concluding Remarks	p. 75
References	p. 75
Large Monochromatic Components in Edge Colorings of Graphs: A Survey	p. 77
Introduction	p. 77
A Remark of Erdos and Rado and Its Extension	p. 77
Colorings from Affine Planes	p. 78
Extending Colorings by Substitutions	p. 79
2-Colorings	p. 79
Type of Spanning Trees, Connectivity, Diameter	p. 79
Gallai-Colorings: Substitutions to 2-Colorings	p. 82
Multicolorings: Basic Results and Proof Methods	p. 83
Complete Bipartite Graphs: Counting Double Stars	p. 83
Fractional Transversals: Füredi's Method	p. 85
Fine Tuning	p. 85
When Both Methods Work: Local Colorings	p. 86
Hypergraphs	p. 88
Multicolorings: Type of Components	p. 89
Components with Large Matching	p. 89
Double Stars	p. 90
Variations	p. 90
Vertex-Coverings by Components	p. 91
Coloring by Group Elements	p. 91
Coloring Geometric Graphs	p. 91
Coloring Noncomplete Graphs	p. 92
References	p. 94
Szlam's Lemma: Mutant Offspring of a Euclidean Ramsey Problem from 1973, with Numerous Applications	p. 97
1973: A Volcano Erupts	p. 97
Some Definitions and More Background	p. 98
What Happened to the Rather Red Coloring Problem from 1973?	p. 101
Distance Graphs	p. 102
Szlam's Lemma, a Connection Between Rather Red Colorings and Chromatic Numbers	p. 104
van der Waerden Numbers, Cyclic van der Waerden Numbers, and a Lower Bound on Them Both	p. 107
References	p. 112
Open Problems in Euclidean Ramsey Theory	p. 115
Introduction	p. 115
Ramsey Sets	p. 117
Unit Distance Graphs	p. 117
More General Distance Graphs	p. 119
References	p. 119
Chromatic Number of the Plane & Its Relatives, History, Problems and Results: An Essay in 11 Parts	p. 121
The Problem	p. 121
The History	p. 124
Polychromatic Number of the Plane & Results Near the Lower Bound	p. 135
De Bruijn-Erdos Reduction to Finite Sets and Results Near the Lower Bound	p. 138
Polychromatic Number of the Plane & Results Near the Upper Bound	p. 141
Continum of 6-Colorings of the Plane	p. 144
Chromatic Number of the Plane in Special Circumstances	p. 148
Colored Space	p. 149
Rational Coloring	p. 151
Axioms of Set Theory and the Chromatic Number of Graphs	p. 153
Predicting the Future	p. 156
References	p. 157
Euclidean Distance Graphs on the Rational Points	p. 163
Definitions	p. 163
The Search for ¿(Rⁿ, 1) Leads to the Search for ¿(Qⁿ, 1)	p. 164
Distances Other Than 1?	p. 167
Problems	p. 172
References	p. 174
Open Problems Session	p. 177
Problems Submitted	p. 179
Problems Submitted	p. 180
Problems on Topological Stability of Chromatic Numbers Submitted	p. 182
Problem on the Gallai-Ramsey Structure, Submitted	p. 183
Problems Involving Triangles, Submitted	p. 185
Problems on Chromatic Number of the Plane and Its Relatives, Submitted	p. 189
Table of Contents provided by Ingram. All Rights Reserved.

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Summary

Table of Contents

Supplemental Materials