Ramsey's theorem

Ramsey's theorem states that finite colorings of fixed-size subsets of an infinite set contain an infinite subset whose subsets of that size are monochromatic.

Set: A set is a collection of distinct objects considered as a whole. The theorem colors subsets drawn from an underlying infinite set.
Infinite pigeonhole principle: The infinite pigeonhole principle says that a finite coloring of an infinite set has an infinite monochromatic subset. It is the one-element case and a recurring step in the general proof.
Finite Ramsey theorem: The finite Ramsey theorem guarantees a monochromatic subset of prescribed size when the original finite set is sufficiently large. Unlike the infinite theorem, it gives finite bounds that grow rapidly with the target.
Ramsey theory: Ramsey theory studies conditions under which large structures contain smaller structures with uniform or ordered behavior. The theorem gives the field its central principle of finding order in arbitrary colorings.
Frank P. Ramsey: Frank P. Ramsey was a British philosopher, mathematician, and economist whose work founded Ramsey theory. His 1930 paper established the theorem now bearing his name.
Subset: A subset is a set whose elements all belong to another set. The theorem seeks an infinite subset whose fixed-size subsets have one color.
Induction: Mathematical induction proves statements about natural numbers from a base case and a step from each case to the next. The classical proof extends the result from smaller subset sizes to larger ones.
Ramsey number: A Ramsey number is the least size of a complete graph that guarantees a monochromatic complete subgraph of a specified size under a given coloring. These numbers quantify the finite theorem's threshold for graph edge colorings.
Ramsey's theorem for graphs: Ramsey's theorem for graphs guarantees a monochromatic complete subgraph of any prescribed finite size in a sufficiently large edge-colored complete graph. This graph formulation is a direct finite application of the general principle.
Paul Erdős: Paul Erdős was a Hungarian mathematician known for foundational work in number theory, combinatorics, and graph theory. His work with George Szekeres developed finite Ramsey theory and its bounds.

Linked from 8 pages