Editing Ramsey's theorem (section)

{{Short description|Statement in mathematical combinatorics}}
{{Use British English|date=October 2020}}

In [[combinatorics]], '''Ramsey's theorem''', in one of its [[Graph theory|graph-theoretic]] forms, states that one will find monochromatic [[clique (graph theory)|cliques]] in any [[graph labeling|edge labelling]] (with colours) of a sufficiently large [[complete graph]]. To demonstrate the theorem for two colours (say, blue and red), let {{mvar|r}} and {{mvar|s}} be any two [[positive integer]]s.{{efn|Some authors restrict the values to be greater than one, for example {{harv|Brualdi|2010}} and {{harv|Harary|1972}}, thus avoiding a discussion of edge colouring a graph with no edges, while others rephrase the statement of the theorem to require, in a [[simple graph]], either an {{mvar|r}}-clique or an {{mvar|s}}-[[Independent set (graph theory)|independent set]], see {{harv|Gross|2008}} or {{harv|Erdős|Szekeres|1935}}. In this form, the consideration of graphs with one vertex is more natural.}} Ramsey's theorem states that there exists a least positive integer {{math|''R''(''r'', ''s'')}} for which every blue-red edge colouring of the [[complete graph]] on {{math|''R''(''r'', ''s'')}} vertices contains a blue clique on {{mvar|r}} vertices or a red clique on {{mvar|s}} vertices. (Here {{math|''R''(''r'', ''s'')}} signifies an integer that depends on both {{mvar|r}} and {{mvar|s}}.)

Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by [[Frank Ramsey (mathematician)|Frank Ramsey]]. This initiated the combinatorial theory now called [[Ramsey theory]], that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of ''monochromatic subsets'', that is, [[subset]]s of connected edges of just one colour.

An extension of this theorem applies to any finite number of colours, rather than just two. More precisely, the theorem states that for any given number of colours, {{mvar|c}}, and any given integers {{math|''n''{{sub|1}}, …, ''n{{sub|c}}''}}, there is a number, {{math|''R''(''n''{{sub|1}}, …, ''n{{sub|c}}'')}}, such that if the edges of a complete graph of order {{math|''R''(''n''{{sub|1}}, …, ''n''{{sub|''c''}})}} are coloured with {{mvar|c}} different colours, then for some {{mvar|i}} between 1 and {{mvar|c}}, it must contain a complete [[Glossary of graph theory#Subgraphs|subgraph]] of order {{mvar|n{{sub|i}}}} whose edges are all colour {{mvar|i}}. The special case above has {{math|1=''c'' = 2}} (and {{math|1=''n''{{sub|1}} = ''r''}} and {{math|1=''n''{{sub|2}} = ''s''}}).