Editing Ramsey theory

{{Short description|Branch of mathematical combinatorics}}
{{for|Ramsey theory of infinite sets|Infinitary combinatorics}}
'''Ramsey theory''', named after the British mathematician and philosopher [[Frank P. Ramsey]], is a branch of the mathematical field of [[combinatorics]] that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a question of the form: "how big must some structure be to guarantee that a particular property holds?"<ref>{{cite book| last1 = Graham | first1 = Ron | last2 = Butler | first2 = Steve | title = Rudiments of Ramsey Theory | edition = 2nd  | year = 2015 | publisher = American Mathematical Society | isbn = 978-0-8218-4156-3 | page = 1 |author-link2=Steve Butler (mathematician)}}</ref>

==Examples==
A typical result in Ramsey theory starts with some mathematical structure that
is then cut into pieces. How big must the original structure be in order to ensure that at least one of the pieces has a given interesting property? This idea can be defined as [[partition regularity]].

For example, consider a [[complete graph]] of order ''n''; that is, there are ''n'' vertices and each vertex is connected to every other vertex by an edge. A complete graph of order 3 is called a triangle. Now colour each edge either red or blue. How large must ''n'' be in order to ensure that there is either a blue triangle or a red triangle? It turns out that the answer is 6. See the article on [[Ramsey's theorem]] for a rigorous [[mathematical proof|proof]].

Another way to express this result is as follows: at any party with at least six people, there are three people who are all either mutual acquaintances (each one knows the other two) or mutual strangers (none of them knows either of the other two). See [[theorem on friends and strangers]].

This also is a special case of Ramsey's theorem, which says that for any given integer ''c'', any given integers ''n''<sub>1</sub>,...,''n''<sub>''c''</sub>, there is a number,   ''R''(''n''<sub>1</sub>,...,''n''<sub>''c''</sub>), such that if the edges of a complete graph of order ''R''(''n''<sub>1</sub>,...,''n''<sub>''c''</sub>) are coloured with ''c'' different colours, then for some ''i'' between 1 and ''c'', it must contain a complete subgraph of order ''n<sub>i</sub>'' whose edges are all colour ''i''. The special case above has ''c'' = 2 and ''n''<sub>1</sub> = ''n''<sub>2</sub> = 3.

==Results==
Two key theorems of Ramsey theory are:

* [[Van der Waerden's theorem]]: For any given ''c'' and ''n'', there is a number ''V'', such that if ''V'' consecutive numbers are coloured with ''c'' different colours,  then it must contain an [[arithmetic progression]] of length ''n'' whose elements are all the same colour.
* [[Hales–Jewett theorem]]: For any given ''n'' and ''c'', there is a number ''H'' such that if the cells of an ''H''-dimensional ''n''×''n''×''n''×...×''n'' cube are coloured with ''c'' colours, there must be one row, column, etc. of length ''n'' all of whose cells are the same colour. That is: a multi-player ''n''-in-a-row [[tic-tac-toe]] cannot end in a draw, no matter how large ''n'' is, and no matter how many people are playing, if you play on a board with sufficiently many dimensions. The Hales–Jewett theorem implies Van der Waerden's theorem.

A theorem similar to van der Waerden's theorem is ''[[Schur's theorem]]'': for any given ''c'' there is a number ''N'' such that if the numbers 1, 2, ..., ''N'' are coloured with ''c'' different colours, then there must be a pair of integers ''x'', ''y'' such that ''x'', ''y'', and ''x''+''y'' are all the same colour.  Many generalizations of this theorem exist, including [[Rado's theorem (Ramsey theory)|Rado's theorem]], [[Rado–Folkman–Sanders theorem]], [[Hindman's theorem]], and the [[Milliken–Taylor theorem]].  A classic reference for these and many other results in Ramsey theory is Graham, Rothschild, Spencer and Solymosi, updated and expanded in 2015 to its first new edition in 25 years.<ref>{{Citation |author-link1=Ronald L. Graham |first1=Ronald L. |last1=Graham 
|author-link2=Bruce L. Rothschild |first2=Bruce L.|last2=Rothschild 
|author-link3=Joel H. Spencer |first3=Joel H. |last3=Spencer 
|author-link4=József Solymosi |first4=József |last4=Solymosi 
|title=Ramsey Theory 
|publisher=John Wiley and Sons 
|location=New York 
|year=2015 
|isbn=978-0470391853 
|edition=3rd }}.</ref>

Results in Ramsey theory typically have two primary characteristics. Firstly, they are [[non-constructive|unconstructive]]: they may show that some structure exists, but they give no process for finding this structure (other than [[brute-force search]]). For instance, the [[pigeonhole principle]] is of this form.  Secondly, while Ramsey theory results do say that sufficiently large objects must necessarily contain a given structure, often the proof of these results requires these objects to be enormously large – bounds that grow [[exponential growth|exponentially]], or even as fast as the [[Ackermann function]] are not uncommon. In some small niche cases, upper and lower bounds are improved, but not in general. In many cases these bounds are artifacts of the proof, and it is not known whether they can be substantially improved. In other cases it is known that any bound must be extraordinarily large, sometimes even greater than any [[primitive recursive]] function; see the [[Paris–Harrington theorem]] for an example. [[Graham's number]], one of the largest numbers ever used in serious mathematical proof, is an upper bound for a problem related to Ramsey theory. Another large example is the [[Boolean Pythagorean triples problem]].<ref>{{Cite journal|last=Lamb|first=Evelyn|date=2016-06-02|title=Two-hundred-terabyte maths proof is largest ever|journal=Nature|language=en|volume=534|issue=7605|pages=17–18|doi=10.1038/nature.2016.19990|pmid=27251254|doi-access=free|bibcode=2016Natur.534...17L }}</ref>

Theorems in Ramsey theory are generally one of the following two types. Many such theorems, which are modeled after Ramsey's theorem itself, assert that in every partition of a large structured object, one of the classes necessarily contains its own structured object, but gives no information about which class this is. In other cases, the reason behind a ''Ramsey-type'' result is that the largest partition class always contains the desired substructure. The results of this latter kind are called either ''density results'' or ''Turán-type result'', after [[Turán's theorem]]. Notable examples include [[Szemerédi's theorem]], which is such a strengthening of van der Waerden's theorem, and the density version of the Hales-Jewett theorem.<ref>{{Citation|author-link1=Hillel Furstenberg|first1=Hillel|last1=Furstenberg|author-link2=Yitzhak Katznelson|first2=Yitzhak|last2=Katznelson |title=A density version of the Hales–Jewett theorem |journal=[[Journal d'Analyse Mathématique]]|volume=57 |issue=1 |year=1991 |pages=64–119 |doi=10.1007/BF03041066 |doi-access= }}.</ref>

==See also==
* [[Ergodic Ramsey theory]]
* [[Extremal graph theory]]
* [[Goodstein's theorem]]
* [[Bartel Leendert van der Waerden]]
* [[Discrepancy theory]]

== References ==
{{Reflist}}

== Further reading ==
*{{Citation |last1=Landman |first1=B. M. |name-list-style=amp |first2=A. |last2=Robertson |title=Ramsey Theory on the Integers |series=Student Mathematical Library |volume=24 |publisher=AMS |location=Providence, RI |isbn=0-8218-3199-2 |year=2004 }}.
*{{Citation |first=F. P. |last=Ramsey |title=On a Problem of Formal Logic |journal=Proceedings of the London Mathematical Society |volume=s2-30 |issue=1 |pages=264–286 |year=1930 |doi=10.1112/plms/s2-30.1.264 }} (behind a paywall).
*{{Citation  | authorlink1 = Paul Erdős | last1 = Erdős | first1 = Paul | authorlink2 = George Szekeres | last2 = Szekeres | first2 = George | title = A combinatorial problem in geometry | journal = [[Compositio Mathematica]] | volume = 2 | pages = 463–470 | orig-year = 1935 | year = 2008 | url = http://www.numdam.org/item?id=CM_1935__2__463_0 | zbl = 0012.27010 | doi = 10.1007/978-0-8176-4842-8_3 | isbn = 978-0-8176-4841-1}}.
*{{Citation |first1=G. |last1=Boolos |first2=J. P. |last2=Burgess |first3=R. |last3=Jeffrey |title=Computability and Logic |location=Cambridge |publisher=Cambridge University Press |edition=5th |year=2007 |isbn=978-0-521-87752-7 |url-access=registration |url=https://archive.org/details/computabilitylog0000bool }}.
* Matthew Katz and Jan Reimann ''[https://bookstore.ams.org/stml-87/ An Introduction to Ramsey Theory: Fast Functions, Infinity, and Metamathematics]'' Student Mathematical Library Volume: 87; 2018; 207 pp; {{ISBN|978-1-4704-4290-3}}

[[Category:Ramsey theory| ]]