Ramsey theory
Encyclopedia
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?"
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?
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 color 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 n1,...,nc, there is a number, R(n1,...,nc), such that if the edges of a complete graph of order R(n1,...,nc) are colored with c different colors, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all color i. The special case above has c = 2 and n1 = n2 = 3.
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 colored with c different colors, then there must be a pair of integers x, y
such that x, y, and x+y are all the same color. Many generalizations of this theorem exist, including 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 et al.
Results in Ramsey theory typically have two primary characteristics. Firstly, they are non-constructive: 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 larger 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.
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. Occasionally, the reason behind such Ramsey-type results is that the largest partition class always contains the desired substructure. A notable example is Szemerédi's theorem
, which is such a strengthening of van der Waerden's theorem. Another example is the density version of Hales-Jewett theorem. The results of this kind are called either density results or Turán-type result, after Turán's theorem
.
Frank P. Ramsey
Frank Plumpton Ramsey was a British mathematician who, in addition to mathematics, made significant and precocious contributions in philosophy and economics before his death at the age of 26...
, is a branch of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
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?"
Examples
A typical result in Ramsey theory starts with some mathematical structure thatis 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?
For example, consider a complete
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
graph
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
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 color 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
Ramsey's theorem
In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph, one will find monochromatic complete subgraphs...
for a rigorous proof
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
.
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
Theorem on friends and strangers
The theorem on friends and strangers is a mathematical theorem in an area of mathematics called Ramsey theory.-Statement:Suppose a party has six people. Consider any two of them. They might be meeting for the first time—in which case we will call them mutual strangers; or they might have met...
.
This also is a special case of Ramsey's theorem
Ramsey's theorem
In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph, one will find monochromatic complete subgraphs...
, which says that for any given integer c, any given integers n1,...,nc, there is a number, R(n1,...,nc), such that if the edges of a complete graph of order R(n1,...,nc) are colored with c different colors, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all color i. The special case above has c = 2 and n1 = n2 = 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 colored with c different colors, then it must contain an arithmetic progressionArithmetic progressionIn mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant...
of length n whose elements are all the same color.
- Hales-Jewett theorem: For any given n and c, there is a number H such that if the cells of a H-dimensional n×n×n×...×n cube are colored with c colors, there must be one row, column, etc. of length n all of whose cells are the same color. That is, if you play on a board with sufficiently many dimensions, then multi-player n-in-a-row tic-tac-toeTic-tac-toeTic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first...
cannot end in a draw, no matter how large n is, and no matter how many people are playing. Hales-Jewett theorem implies Van der Waerden's theorem.
A theorem similar to van der Waerden's theorem is Schur's theorem
Schur's theorem
In discrete mathematics, Schur's theorem is either of two different theorems of the mathematician Issai Schur. In differential geometry, Schur's theorem is a theorem of A. Schur...
: for any given c there is a number N such that if the numbers 1, 2, ..., N are colored with c different colors, then there must be a pair of integers x, y
such that x, y, and x+y are all the same color. Many generalizations of this theorem exist, including Rado's Theorem
Rado's theorem
In mathematics, Rado's theorem is a result about harmonic functions, named after Tibor Radó. Informally, it says that any "nice looking" shape without holes can be smoothly deformed into a disk....
, Rado-Folkman-Sanders theorem, Hindman's theorem
IP set
In mathematics, an IP set is a set of natural numbers which contains all finite sums of some infinite set.The finite sums of a set D of natural numbers are all those numbers that can be obtained by adding up the elements of some finite nonempty subset of D.The set of all finite sums over D is often...
, and the Milliken-Taylor theorem. A classic reference for these and many other results in Ramsey theory is Graham et al.
Results in Ramsey theory typically have two primary characteristics. Firstly, they are non-constructive: 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
Exponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
, or even as fast as the Ackermann function
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...
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 larger than any primitive recursive function; see the Paris-Harrington theorem for an example. Graham's number
Graham's number
Graham's number, named after Ronald Graham, is a large number that is an upper bound on the solution to a certain problem in Ramsey theory.The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977,...
, 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. Occasionally, the reason behind such Ramsey-type results is that the largest partition class always contains the desired substructure. A notable example is Szemerédi's theorem
Szemerédi's theorem
In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...
, which is such a strengthening of van der Waerden's theorem. Another example is the density version of Hales-Jewett theorem. The results of this kind are called either density results or Turán-type result, after Turán's theorem
Turán's theorem
In graph theory, Turán's theorem is a result on the number of edges in a Kr+1-free graph.An n-vertex graph that does not contain any -vertex clique may be formed by partitioning the set of vertices into r parts of equal or nearly-equal size, and connecting two vertices by an edge whenever they...
.
See also
- Bartel Leendert van der WaerdenBartel Leendert van der WaerdenBartel Leendert van der Waerden was a Dutch mathematician and historian of mathematics....
- CombinatoricsCombinatoricsCombinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
- Goodstein's theoremGoodstein's theoremIn mathematical logic, Goodstein's theorem is a statement about the natural numbers, made by Reuben Goodstein, which states that every Goodstein sequence eventually terminates at 0. showed that it is unprovable in Peano arithmetic...
- Graham's numberGraham's numberGraham's number, named after Ronald Graham, is a large number that is an upper bound on the solution to a certain problem in Ramsey theory.The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977,...
- Ergodic Ramsey theoryErgodic Ramsey theoryErgodic Ramsey theory is a branch of mathematics where problems motivated by additive combinatorics are proven using ergodic theory.Ergodic Ramsey theory arose shortly after Endre Szemerédi's proof that a set of positive upper density contains arbitrarily long arithmetic progressions, when Hillel...
- Extremal graph theoryExtremal graph theoryExtremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth...