Ramsey theory

Ramsey theory studies when sufficiently large structures must contain orderly substructures, regardless of how their elements are arranged or colored.

Ramsey's theorem: A theorem guaranteeing monochromatic complete subgraphs in sufficiently large edge-colored complete graphs. It states the basic finite guarantee behind graph Ramsey theory.
Graph theory: The mathematical study of vertices, edges, and the relationships represented by them. Graph Ramsey theory applies its guarantees to colored edges and vertex configurations.
Frank P. Ramsey: A British mathematician, philosopher, and economist whose 1930 theorem established a foundational result in combinatorics. His theorem gave the subject its name and its first general framework.
Van der Waerden's theorem: A theorem stating that every finite coloring of the integers contains a monochromatic arithmetic progression of any prescribed finite length. It applies the unavoidable-pattern principle to arithmetic progressions.
R(3,3): The smallest number of vertices forcing a monochromatic triangle in every red-blue coloring of a complete graph’s edges; it equals six. This is the smallest nontrivial classical Ramsey number and a solved benchmark.
Ramsey number: The least size that guarantees a specified monochromatic substructure in every coloring. It quantifies how large a structure must be before the guarantee holds.
Edge coloring: An assignment of colors to the edges of a graph. The basic finite Ramsey problem asks what colored edges force.
On a Problem of Formal Logic: Frank Ramsey’s 1930 paper proving a theorem about regularity in sufficiently large structures. This paper introduced the result from which Ramsey theory developed.
Schur's theorem: A theorem stating that every finite coloring of the positive integers contains monochromatic integers x, y, and x+y. It shows that coloring integers cannot eliminate every simple additive equation.
R(4,4): The smallest number of vertices forcing a monochromatic four-vertex complete graph in every red-blue edge coloring; it is known to be 18. Its exact value illustrates the difficulty that quickly appears beyond triangles.

Linked from 19 pages