Ramsey's Theorem

A vast generalization of the pigeonhole principle formulated by the English logician F.P. Ramsey which concerns the minimum size a set must be in order to guarantee that some category is full when the t-subsets of a set are being placed into categories.

Let q1,q2, ... qn and t be positive integers with each qi greater than or equal to t. There exists a least positive integer R(q1,q2, ... qn;t) such that if the t-subsets of a set with cardinality at least R(q1,q2, ... qn;t) are placed into n categories, then for some i there are qi elements of the set which have all of their t-subsets in the i-th category.

Ramsey numbers are difficult to determine, and almost all of the known ramsey numbers are for t = 2. Ramsey numbers with t = 2 can be given a graphical significance in terms of coloring the edges of a graph, an edge in the graph corresponding to a 2-subset, and the colors being categories.

As an example, the Ramsey number R(3,3;2) = 6 means that if all of the edges of a complete graph on 6 vertices are colored either red or blue, there must be either a red triangle, or a blue triangle.

Recurrence Relation

A means of generating an integer sequence. One starts with a small number of initial values, and then applies a recurrence rule. See, for example, the Fibonacci sequence.

Regular polytope

One in which there is a symmetry taking any flag into any other flag. In three dimensions, these are the five Platonic solids. In four dimensions, there are six different regular polytopes. In any higher dimension, there are only three: the simplex, the hypercube, and the cross polytope.


A set of elements with two operations defined on it, the first (usually called addition) makes the set an abelian group . The two operations are related by the distributive laws

x(y + z) = xy + xz and (y + z)x = yx + zx

If the second operation (usually called multiplication) is commutative we have a commutative ring if there is an identity element with respect to the second operation, we have a ring with one , and if there are no zero divisors in the ring we have an integral domain.

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

An On-line Dictionary of Combinatorics