Editing Ramsey's theorem (section)

== Extensions of the theorem ==
=== Infinite graphs ===
A further result, also commonly called ''Ramsey's theorem'', applies to infinite graphs. In a context where finite graphs are also being discussed it is often called the "Infinite Ramsey theorem". As intuition provided by the pictorial representation of a graph is diminished when moving from finite to infinite graphs, theorems in this area are usually phrased in [[set theory|set-theoretic]] terminology.<ref>{{cite web |author=Gould |first=Martin |title=Ramsey Theory |url=http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf |archive-url=https://web.archive.org/web/20220130151921/http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf |archive-date=2022-01-30 |website=[[Mathematical Institute, University of Oxford]]}}</ref>

:''Theorem.'' Let <math>X</math> be some infinite set and colour the elements of <math>[X]^n</math> (the subsets of <math>X</math> of size <math>n</math>) in <math>c</math> different colours. Then there exists some infinite subset <math>M</math> of <math>X</math> such that the size <math>n</math> subsets of <math>M</math> all have the same colour.

''Proof'': The proof is by induction on {{mvar|n}}, the size of the subsets. For {{math|1=''n'' = 1}}, the statement is equivalent to saying that if you split an infinite set into a finite number of sets, then one of them is infinite. This is evident. Assuming the theorem is true for {{math|''n'' ≤ ''r''}}, we prove it for {{math|1=''n'' = ''r'' + 1}}. Given a {{mvar|c}}-colouring of the {{math|(''r'' + 1)}}-element subsets of {{mvar|X}}, let {{math|''a''{{sub|0}}}} be an element of {{mvar|X}} and let {{math|1=''Y'' = ''X ''  \ {''a''{{sub|0}}<nowiki>}</nowiki>.}} We then induce a {{mvar|c}}-colouring of the {{mvar|r}}-element subsets of {{mvar|Y}}, by just adding {{math|''a''{{sub|0}}}} to each {{mvar|r}}-element subset (to get an {{math|(''r'' + 1)}}-element subset of {{mvar|X}}). By the induction hypothesis, there exists an infinite subset {{math|''Y''{{sub|1}}}} of {{mvar|Y}} such that every {{mvar|r}}-element subset of {{math|''Y''{{sub|1}}}} is coloured the same colour in the induced colouring. Thus there is an element {{math|''a''{{sub|0}}}} and an infinite subset {{math|''Y''{{sub|1}}}} such that all the {{math|(''r'' + 1)}}-element subsets of {{mvar|X}} consisting of {{math|''a''{{sub|0}}}} and {{mvar|r}} elements of {{math|''Y''{{sub|1}}}} have the same colour. By the same argument, there is an element {{math|''a''{{sub|1}}}} in {{math|''Y''{{sub|1}}}} and an infinite subset {{math|''Y''{{sub|2}}}} of {{math|''Y''{{sub|1}}}} with the same properties. Inductively, we obtain a sequence {{math|{''a''{{sub|0}}, ''a''{{sub|1}}, ''a''{{sub|2}}, …} }} such that the colour of each {{math|(''r'' + 1)}}-element subset {{math|(''a''{{sub|''i''(1)}}, ''a''{{sub|''i''(2)}}, …, ''a''{{sub|''i''(''r'' + 1)}})}} with {{math|''i''(1) < ''i''(2) < … < ''i''(''r'' + 1)}} depends only on the value of {{math|''i''(1)}}. Further, there are infinitely many values of {{math|''i''(''n'')}} such that this colour will be the same. Take these {{math|''a''{{sub|''i''(''n'')}}}}'s to get the desired monochromatic set.

A stronger but unbalanced infinite form of Ramsey's theorem for graphs, the [[Erdős–Dushnik–Miller theorem]], states that every infinite graph contains either a [[countable set|countably infinite]] independent set, or an infinite clique of the same [[cardinality]] as the original graph.<ref>{{cite journal|last1=Dushnik|first1=Ben|last2=Miller|first2=E. W.|doi=10.2307/2371374|journal=American Journal of Mathematics|jstor=2371374|mr=4862|pages=600–610|title=Partially ordered sets|volume=63|year=1941|issue=3|hdl=10338.dmlcz/100377|hdl-access=free}}. See in particular Theorems 5.22 and 5.23.</ref>

==== Infinite version implies the finite ====
It is possible to deduce the finite Ramsey theorem from the infinite version by a [[proof by contradiction]]. Suppose the finite Ramsey theorem is false. Then there exist integers {{mvar|c}}, {{mvar|n}}, {{mvar|T}} such that for every integer {{mvar|k}}, there exists a {{mvar|c}}-colouring of {{math|[''k'']{{sup|(''n'')}}}} without a monochromatic set of size {{mvar|T}}. Let {{mvar|C{{sub|k}}}} denote the {{mvar|c}}-colourings of {{math|[''k'']{{sup|(''n'')}}}} without a monochromatic set of size {{mvar|T}}.

For any {{mvar|k}}, the restriction of a colouring in {{math|''C''{{sub|''k''+1}}}} to {{math|[''k'']{{sup|(''n'')}}}} (by ignoring the colour of all sets containing {{math|''k'' + 1}}) is a colouring in {{mvar|C{{sub|k}}}}. Define {{tmath|C^1_k}} to be the colourings in {{mvar|C{{sub|k}}}} which are restrictions of colourings in {{math|''C''{{sub|''k''+1}}}}. Since {{math|''C''{{sub|''k''+1}}}} is not empty, neither is {{tmath|C^1_k}}.

Similarly, the restriction of any colouring in {{tmath|C^1_{k+1} }} is in {{tmath|C^1_k}}, allowing one to define {{tmath|C^2_k}} as the set of all such restrictions, a non-empty set. Continuing so, define {{tmath|C^m_k}} for all integers {{mvar|m}}, {{mvar|k}}.

Now, for any integer {{mvar|k}},
:<math>C_k\supseteq C^1_k\supseteq C^2_k\supseteq \cdots</math>
and each set is non-empty. Furthermore, {{mvar|C{{sub|k}}}} is finite as
:<math>|C_k|\le c^{\frac{k!}{n!(k-n)!}}</math>
It follows that the intersection of all of these sets is non-empty, and let
:<math>D_k=C_k\cap C^1_k\cap C^2_k\cap \cdots</math>
Then every colouring in {{mvar|D{{sub|k}}}} is the restriction of a colouring in {{math|''D''{{sub|''k''+1}}}}. Therefore, by unrestricting a colouring in {{mvar|D{{sub|k}}}} to a colouring in {{math|''D''{{sub|''k''+1}}}}, and continuing doing so, one constructs a colouring of <math>\mathbb N^{(n)}</math> without any monochromatic set of size {{mvar|T}}. This contradicts the infinite Ramsey theorem.

If a suitable topological viewpoint is taken, this argument becomes a standard [[compactness theorem|compactness argument]] showing that the infinite version of the theorem implies the finite version.<ref>{{Cite book|title=Graph Theory|last=Diestel|first=Reinhard|publisher=Springer-Verlag|year=2010|isbn=978-3-662-53621-6|edition=4|location=Heidelberg|pages=209–2010|chapter=Chapter 8, Infinite Graphs}}</ref>

=== Hypergraphs ===
The theorem can also be extended to [[hypergraph]]s. An {{mvar|m}}-hypergraph is a graph whose "edges" are sets of {{mvar|m}} vertices – in a normal graph an edge is a set of 2 vertices. The full statement of Ramsey's theorem for hypergraphs is that for any integers {{mvar|m}} and {{mvar|c}}, and any integers {{math|''n''{{sub|1}}, …, ''n{{sub|c}}''}}, there is an integer {{math|''R''(''n''{{sub|1}}, …, ''n{{sub|c}}''; m)}} such that if the hyperedges of a complete {{mvar|m}}-hypergraph of order {{math|''R''(''n''{{sub|1}}, …, ''n{{sub|c}}''; ''m'')}} are coloured with {{mvar|c}} different colours, then for some {{mvar|i}} between 1 and {{mvar|c}}, the hypergraph must contain a complete sub-{{mvar|m}}-hypergraph of order {{mvar|n{{sub|i}}}} whose hyperedges are all colour {{mvar|i}}. This theorem is usually proved by induction on {{mvar|m}}, the 'hyper-ness' of the graph. The base case for the proof is {{math|1=''m'' = 2}}, which is exactly the theorem above.

For {{math|1=''m'' = 3}} we know the exact value of one non-trivial Ramsey number, namely {{math|1=''R''(4, 4; 3) = 13}}. This fact was established by Brendan McKay and Stanisław Radziszowski in 1991.<ref>{{Cite journal |last1=McKay |first1=Brendan D. |last2=Radziszowski |first2=Stanislaw P. |date=1991 |title=The First Classical Ramsey Number for Hypergraphs is Computed |journal=Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'91 |pages=304–308}}</ref> Additionally, we have: {{math|''R''(4, 5; 3) ≥ 35}},<ref name=Dybizbański2018>{{Cite journal
| last=Dybizbański | first=Janusz
| date=2018-12-31
| title=A lower bound on the hypergraph Ramsey number R(4,5;3)
| journal=Contributions to Discrete Mathematics
| language=en
| volume=13
| issue=2
| doi=10.11575/cdm.v13i2.62416 | doi-access=free
| issn=1715-0868}}</ref> {{math|''R''(4, 6; 3) ≥ 63}} and {{math|''R''(5, 5; 3) ≥ 88}}.<ref name=Dybizbański2018 />

=== Directed graphs ===
It is also possible to define Ramsey numbers for ''directed'' graphs; these were introduced by {{harvs|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=L.|last2=Moser|year=1964|txt}}. Let {{math|''R''(''n'')}} be the smallest number {{mvar|Q}} such that any complete graph with singly directed arcs (also called a "tournament") and with {{math|≥ ''Q''}} nodes contains an acyclic (also called "transitive") {{mvar|n}}-node subtournament.

This is the directed-graph analogue of what (above) has been called {{math|''R''(''n'', ''n''; 2)}}, the smallest number {{mvar|Z}} such that any 2-colouring of the edges of a complete ''un''directed graph with {{math|≥ ''Z''}} nodes, contains a monochromatic complete graph on n nodes. (The directed analogue of the two possible arc ''colours'' is the two ''directions'' of the arcs, the analogue of "monochromatic" is "all arc-arrows point the same way"; i.e., "acyclic.")

We have {{math|1=''R''(0) = 0}}, {{math|1=''R''(1) = 1}}, {{math|1=''R''(2) = 2}}, {{math|1=''R''(3) = 4}}, {{math|1=''R''(4) = 8}}, {{math|1=''R''(5) = 14}}, {{math|1=''R''(6) = 28}}, and {{math|34 ≤ ''R''(7) ≤ 47}}.<ref>{{citation|last1=Smith|first1=Warren D.|title=Partial Answer to Puzzle #27: A Ramsey-like quantity|url=http://rangevoting.org/PuzzRamsey.html|access-date=2020-06-02|last2=Exoo|first2=Geoff}}</ref><ref>{{cite arXiv|last1=Neiman|first1=David|last2=Mackey|first2=John|last3=Heule|first3=Marijn|date=2020-11-01|title=Tighter Bounds on Directed Ramsey Number R(7)|class=math.CO|eprint=2011.00683}}</ref>

=== Uncountable cardinals ===
{{Main|Partition calculus}}
In terms of the partition calculus, Ramsey's theorem can be stated as <math>\alef_0\rightarrow(\alef_0)^n_k</math> for all finite ''n'' and ''k''. [[Wacław Sierpiński]] showed that the Ramsey theorem does not extend to graphs of size <math>\alef_1</math> by showing that <math>2^{\alef_0}\nrightarrow(\alef_1)^2_2</math>. In particular, the [[continuum hypothesis]] implies that <math>\alef_1\nrightarrow(\alef_1)^2_2</math>. [[Stevo Todorčević]] showed that in fact in [[ZFC]], <math>\alef_1\nrightarrow[\alef_1]^2_{\alef_1}</math>, a much stronger statement than <math>\alef_1\nrightarrow(\alef_1)^2_2</math>. [[Justin T. Moore]] has strengthened this result further. On the positive side, a [[Ramsey cardinal]] is a [[large cardinal]] <math>\kappa</math> axiomatically defined to satisfy the related formula: <math>\kappa\rightarrow(\kappa)^{<\omega}_2</math>. The existence of Ramsey cardinals cannot be proved in ZFC.