For any given numbers of colors and target structure sizes, there exists a threshold size beyond which any coloring of the edges of a sufficiently large complete graph must contain a monochromatic complete subgraph of the target size. Proved by Frank Ramsey, it founded Ramsey theory, the study of the unavoidable order that appears within sufficiently large structures.
Facts
StatementFor any given sizes r and s, there is a smallest number n such that coloring the edges of a complete graph on n vertices in two colors always produces either a complete subgraph on r vertices entirely in the first color or a complete subgraph on s vertices entirely in the second color. More generally, coloring the edges of a sufficiently large complete graph in finitely many colors always produces a monochromatic complete subgraph of any specified size. 2 Classification
Statement Form Connections
Sources
1. Wikipedia: Ramsey's theorem
WikipediaLead section, statement-form referenceQuote, Lead section, statement-form reference
Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices.
2. Ramsey's Theorem (Wikipedia)
Wikimedia FoundationLead section
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling of a sufficiently large complete graph.
References list
Ramsey, F. P. (1930), "On a problem of formal logic", Proceedings of the London Mathematical Society, 30: 264-286
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.