Math 2.0

statement theorem

Ramsey's theorem

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.

Explanations

L1 human

Complete disorder is impossible in a large enough structure. If you colour the edges of a large complete graph with two colours, a large clique of one colour always appears.

What this node 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 node is. They do not measure its truth.

What this needs

To read this node, read these 3 nodes in this order. The foundations come first, and the list ends with this node.

Clique, definition, no evidence levelCliquedefinitionComplete graph, example, no evidence levelComplete graphexampleRamsey's theorem, statement, no evidence levelRamsey's theoremstatement
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Clique definition
  2. Complete graph example
  3. Ramsey's theorem statement

Sources

  1. Web https://en.wikipedia.org/wiki/Ramsey's_theorem, lead section

What links here

No node links to this node yet.