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.
--back to
combinatorics--