Ramsey Theory

The mathematical study of combinatorial objects in which a certain degree of order must occur as the scale of the object becomes large. Ramsey theory is named after Frank Plumpton Ramsey, who did seminal work in this area before his untimely death at age 26 in 1930. The theory was subsequently developed extensively by Erdős.

The classical problem in Ramsey theory is the party problem, which asks the minimum number of guests 👁 R(m,n)
that must be invited so that at least 👁 m
will know each other (i.e., there exists a clique of order 👁 m
) or at least 👁 n
will not know each other (i.e., there exists an independent set of order 👁 n
. Here, 👁 R(m,n)
is called a Ramsey number.

A typical result in Ramsey theory states that if some mathematical object is partitioned into finitely many parts, then one of the parts must contain a subobject of an interesting kind. For example, it is known that if 👁 n
is large enough and 👁 V
is an 👁 n
-dimensional vector space over the field of integers (mod 👁 p
), then however 👁 V
is partitioned into 👁 r
pieces, one of the pieces contains an affine subspace of dimension 👁 d
.

See also

Extremal Graph Theory, Graham's Number, Happy End Problem, Knuth Up-Arrow Notation, Party Problem, Ramsey Number, Structural Ramsey Theory

Explore with Wolfram|Alpha

References

Burr, S. A. "Generalized Ramsey Theory for Graphs--A Survey." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). New York: Springer-Verlag, pp. 52-75, 1974.Erdős, P. and Szekeres, G. "On Some Extremum Problems in Elementary Geometry." Ann. Univ. Sci. Budapest Eőtvős Soc. Math. 3-4, 53-62, 1961.Graham, R. L. and Nešetril, J. "Ramsey Theory in the Work of Paul Erdős." In The Mathematics of Paul Erdős (Ed. R. L. Graham and J. Nešetril). Heidelberg, Germany: Springer-Verlag, 1996.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 51-57, 1998.

Referenced on Wolfram|Alpha

Ramsey Theory

Cite this as:

Weisstein, Eric W. "Ramsey Theory." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RamseyTheory.html

Subject classifications