Ramsey Theory
Ramsey theory studies how complete disorder is impossible: any sufficiently large structure must contain a highly organized substructure.
Definition
The branch of combinatorics asking how large a structure must be to guarantee that any partition or coloring of it yields a monochromatic or otherwise prescribed substructure.
Scope
The area covers Ramsey's theorem for graphs and hypergraphs and its quantitative Ramsey numbers, partition results for the integers such as Schur's, van der Waerden's, and Hales-Jewett theorems, and the abstract structural Ramsey theory of parameter sets. It exemplifies the extremal-combinatorial principle that large enough systems cannot avoid order.
Sub-topics
Core questions
- How large must a structure be to force an unavoidable ordered substructure?
- What are the exact or approximate thresholds, the Ramsey numbers, for these guarantees?
- How do partition theorems for the integers guarantee arithmetic patterns?
- Which abstract families of structures satisfy a Ramsey property?
Key concepts
- Ramsey's theorem
- Ramsey numbers
- Monochromatic substructures
- Van der Waerden's theorem
- Schur's theorem
- Hales-Jewett theorem
Clinical relevance
Ramsey-type guarantees of unavoidable structure inform lower-bound arguments in theoretical computer science, the analysis of large networks, and additive number theory, while the gap between known bounds drives the probabilistic method.
History
Frank Ramsey's 1930 theorem on partitions, originally proved for a question in logic, was recognized by Erdos and Szekeres as the seed of a broad theory of unavoidable structure that grew through the 20th century.
Key figures
- Frank Ramsey
- Paul Erdos
- Bartel van der Waerden
Related topics
Seminal works
- graham1990
- landman2003
Frequently asked questions
- What is the slogan of Ramsey theory?
- Complete disorder is impossible: any sufficiently large system, however arranged, must contain a sizable orderly part.
- Why are Ramsey numbers hard to compute?
- The number of colorings to check grows astronomically, and even small Ramsey numbers such as R(5,5) remain unknown despite intense effort.