Math 2.0

Combinatorics Ramsey theory Theorem

Ramsey's theorem

Builds on Complete graphClique

Statement

Let rr and ss be positive integers. Then there is a positive integer nn with this property. Colour each edge of the complete graph KnK_n blue or red, in any way. Then there is a blue clique with rr vertices or a red clique with ss vertices.

Remarks

The least such nn is the Ramsey number R(r,s)R(r, s). The proof gives the bound R(r,s)≤R(r−1,s)+R(r,s−1)R(r, s) \le R(r - 1, s) + R(r, s - 1), by induction on r+sr + s. The theorem also holds for any finite number of colours.

History

Frank Ramsey proved the first version of the theorem in a 1930 paper on formal logic. This result started the field now called Ramsey theory.

Reading path

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

Show the path as a graph
Clique, definition, no evidence levelCliquedefinitionComplete graph, example, no evidence levelComplete graphexampleRamsey's theorem, statement, no evidence levelRamsey's theoremstatement
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. Clique definition
  2. Complete graph example
  3. Ramsey's theorem statement

Where this leads

3 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Ramsey's_theorem, lead section
About this page
Tag00TQV3F5S4
URIm2://00TQV3F5S4
Kindstatement, theorem
WritingW1 stated
MSC05D10, 05C55
StatusThis copy of the site has no build data. Run m2 status 00TQV3F5S4.
UsesComplete graph, Clique
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge about out: the concepts that the statement is about (0 of 1)
  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

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

What links here

Used by