Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. Problems in Ramsey theory typically ask a question of the form: "how many elements of some structure must there be to guarantee that a particular property will hold?"
Contents

Examples 1

Results 2

See also 3

Notes 4

References 5
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 every edge 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 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 (each one does not know 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_{1},...,n_{c}, there is a number, R(n_{1},...,n_{c}), such that if the edges of a complete graph of order R(n_{1},...,n_{c}) are coloured with c different colours, then for some i between 1 and c, it must contain a complete subgraph of order n_{i} whose edges are all colour i. The special case above has c = 2 and n_{1} = n_{2} = 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 a Hdimensional 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, if you play on a board with sufficiently many dimensions, then multiplayer ninarow tictactoe cannot end in a draw, no matter how large n is, and no matter how many people are playing. HalesJewett 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, RadoFolkmanSanders theorem, Hindman's theorem, and the MillikenTaylor theorem. A classic reference for these and many other results in Ramsey theory is Graham, Rothschild and Spencer.^{[1]}
Results in Ramsey theory typically have two primary characteristics. Firstly, they are nonconstructive: 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 exponentially, or even as fast as the Ackermann function are not uncommon. 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 ParisHarrington 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.
Theorems in Ramsey theory are generally one of the two types. Many 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 a large structured subobject, but give no information about which class this is. Occasionally, the reason behind such Ramseytype results is that the largest partition class always contains the desired substructure. The results of this kind are called either density results or Turántype 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 HalesJewett theorem.^{[2]}
See also
Notes
References

Landman, B. M. & Robertson, A. (2004), Ramsey Theory on the Integers, Student Mathematical Library 24, Providence, RI: AMS, .

Ramsey, F. P. (1930), "On a Problem of Formal Logic", Proceedings London Mathematical Society, s230 (1): 264–286, .

Erdös, P. & Szekeres, G. (1935), "A combinatorial problem in geometry", Compositio Mathematica 2: 463–470 .

Boolos, G.; Burgess, J. P.; Jeffrey, R. (2007), Computability and Logic (5th ed.), Cambridge: Cambridge University Press, .
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.