Math 2.0

Combinatorics Theorem

Ramsey's theorem for colourings of s-subsets with several colours

Builds on Ramsey number

Statement

Let rr and ss be positive integers. Let h1,h2,…,hrh_1, h_2, \dots, h_r be integers with hi≥sh_i \ge s for each i=1,…,ri = 1, \dots, r.

Then there is a least positive integer R(s:h1,…,hr)R(s : h_1, \dots, h_r) with this property. Let n≥R(s:h1,…,hr)n \ge R(s : h_1, \dots, h_r). Colour every ss-element subset of {1,…,n}\{1, \dots, n\} with one of rr colours, in any way. Then there is a colour α∈{1,…,r}\alpha \in \{1, \dots, r\} and a set H⊆{1,…,n}H \subseteq \{1, \dots, n\} with ∣H∣=hα|H| = h_\alpha, such that every ss-element subset of HH has colour α\alpha.

Remarks

For s=2s = 2 the ss-subsets are the edges of a complete graph, and the number is a generalised Ramsey number for rr colours.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Ramsey number definition
  2. Ramsey's theorem for colourings of s-subsets with several colours statement

Further reading

  1. Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_ramsey_theorem.ptx#L11, source/s_ramsey_theorem.ptx:11
About this page
TagYSZ82MRXT8
URIm2://YSZ82MRXT8
Kindstatement, theorem
WritingW0 stub
MSC05D10
StatusThis copy of the site has no build data. Run m2 status YSZ82MRXT8.
UsesRamsey number
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.