📐 Ramsey

For all positive integers $s, t$, there exists a minimum $R(s,t)$ such that every red-blue edge-coloring of $K_n$ with $n \\geq R(s,t)$ contains a red $K_s$ or a blue $K_t$.

Proof: Induction: $R(s,1) = R(1,t) = 1$. For $s,t > 1$: take $n = R(s-1,t) + R(s,t-1)$. Pick vertex $v$; partition neighbors by edge color. Red neighbors form set of size $\\geq R(s-1,t)$ or blue neighbors $\\geq R(s,t-1)$. By induction, find red $K_{s-1}$ or blue $K_t$ in red neighborhood (add $v$ for ...

From: Introduction to Graph Theory

Learn more: https://west-graphs-deploy.vercel.app/#/section/25

Explore all courses: https://mathacademy-cyan.vercel.app