Subscribe to the weekly news from TrueShelf

0

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\).

Related Content