Editing Ramsey's theorem (section)

=== 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>