# R

## 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 * q*_{1},q_{2}, ... q_{n} and *t* be positive integers with
each * q*_{i} greater than or equal to *t*. There exists a
least positive integer * R(q*_{1},q_{2}, ... q_{n};t) such that if the
*t*-subsets of a set with cardinality at least
* R(q*_{1},q_{2}, ... q_{n};t) are placed into *n* categories, then
for some *i* there are *q*_{i} 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.

## Ring

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