Subscribe to the weekly news from TrueShelf

## Basics of Ramsey's theory

A special case of Ramsey's theorem states that for any pair of positive integers $(r,s)$, there exists a least positive integer $R(r,s)$ such that for any complete graph on $R(r,s)$ vertices, whose edges are colored red or blue, there exists either a complete subgraph on $r$ vertices which is entirely blue, or a complete subgraph on $s$ vertices which is entirely red. Here $R(r,s)$ represents the smallest integer for which the theorem holds.

• What is the value of the Ramsey number $R(K_2,K_9)$ ?

• Let $C_4$ be a cycle on $4$ vertices. Prove that the Ramsey number $R(C_4,C_4)=6$.

0

0

0

0

0

0

0

0

0

0