Math 2.0

Combinatorics Definition

Ramsey number

Definition

Let rr and ss be positive integers. The Ramsey number R(r,s)R(r, s) is the least 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

Such an nn exists by Ramsey's theorem. R(r,s)=R(s,r)R(r, s) = R(s, r) and R(r,2)=rR(r, 2) = r. The theorem on friends and strangers gives R(3,3)=6R(3, 3) = 6. With more colours there are similar numbers, for example R(3,3,3)=17R(3, 3, 3) = 17.

Further reading

  1. Web https://en.wikipedia.org/wiki/Ramsey's_theorem, lead section
About this page
Tag01DSVCRF6X
URIm2://01DSVCRF6X
Kinddefinition
WritingW1 stated
MSC05C55, 05D10
DefinesRamsey number

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (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.