Mathematics.

extremal combinatorics

Ramsey Theory

Combinatorics30 minDifficulty3 out of 10

You should know: pigeonhole principle, graph basics

Overview

Ramsey theory studies the conditions under which order or structure must appear within any sufficiently large system, no matter how it is arranged — informally captured by the slogan 'complete disorder is impossible.' The classic setting colors the edges of a complete graph with two colors and asks how large the graph must be to guarantee a monochromatic complete subgraph of a given size. The Ramsey number R(m,n) is the smallest N such that any 2-coloring of the edges of the complete graph on N vertices contains either a red K_m or a blue K_n. Ramsey numbers grow explosively and are notoriously difficult to compute exactly.

Intuition

The famous 'party problem' asks: what is the smallest number of people you need at a party to guarantee either 3 mutual acquaintances or 3 mutual strangers? Model people as vertices of a complete graph and color each edge red (acquaintance) or blue (stranger). R(3,3)=6 means that among any 6 people, you're guaranteed to find such a monochromatic triangle, but with only 5 people you can arrange acquaintances/strangers to avoid it entirely (the 5-cycle coloring is the standard counterexample). This captures the Ramsey-theoretic idea that once a structure gets large enough, some pattern is forced to emerge — you cannot avoid all order forever.

Formal Definition

Definition

The Ramsey number R(m,n) is defined via complete graph edge-colorings:

R(m,n)=min⁡{N:every red/blue coloring of KN’s edges contains a red Km or a blue Kn}R(m,n) = \min\{ N : \text{every red/blue coloring of } K_N \text{'s edges contains a red } K_m \text{ or a blue } K_n \}
Definition of the Ramsey number
R(3,3)=6R(3,3) = 6
The classic 'party problem' Ramsey number

Worked Examples

  1. Model the 6 people as vertices of K_6, with edges colored red (know each other) or blue (strangers).

    K6 has (62)=15 edgesK_6 \text{ has } \binom{6}{2} = 15 \text{ edges}

  2. R(3,3)=6 is the established minimum N for which every such 2-coloring must contain a monochromatic K_3 (a triangle all one color).

    R(3,3)=6R(3,3) = 6

Answer: Since R(3,3)=6, any 2-coloring of K_6's edges contains a monochromatic triangle — guaranteeing 3 mutual acquaintances or 3 mutual strangers.

Practice Problems

Difficulty 4/10

How many edges does the complete graph K_6 have?

Difficulty 3/10

What is the value of R(3,3)?

Difficulty 5/10

A group has 5 people, and their acquaintance relationships are colored so that the 'knows' edges form exactly a 5-cycle. Does this group contain 3 mutual acquaintances?

Quiz

The Ramsey number R(3,3) equals:
Ramsey theory's core idea, often summarized as 'complete disorder is impossible,' means:

Summary

  • Ramsey theory guarantees that sufficiently large structures must contain some specific pattern, no matter how they are arranged.
  • The Ramsey number R(m,n) is the smallest N such that every red/blue coloring of K_N's edges contains a red K_m or blue K_n.
  • R(3,3)=6 is the classic verified case: 6 people always contain 3 mutual acquaintances or 3 mutual strangers, but 5 people do not.

References

  1. WebsiteWikipedia — Ramsey's theorem