= Ramsey number
{c}
{title2=$R(s,t)$}
For <positive integers> $s,t$, the Ramsey number $R(s,t)$ is the least <integer> $n$ such that every red-blue <edge coloring> of the <complete graph> $K_n$ contains either a red <clique> on $s$ <vertices> or a blue <clique> on $t$ <vertices>. The <complete graph> $K_n$ has all $\binom n2$ <unordered pairs> as <edges>; every <edge> gets exactly one color, with no requirement that incident <edges> have different colors. The definition and its <graph> interpretation appear in https://www.isibang.ac.in/~d.yogesh/Course_Notes/DM1/Ch5.S3.html[D. Yogeshwaran's Discrete Mathematics notes, section 5.3].
For example, $R(3,3)$ asks how many <vertices> force a <monochromatic> <triangle in a graph>. Swapping colors gives $R(s,t)=R(t,s)$. Also $R(2,t)=t$: either a red <edge> exists, or all <edges> are blue. On $t-1$ <vertices>, an all-blue coloring avoids both a red <edge> and a blue $t$-<clique>. Under the convention that a one-<vertex> <clique> qualifies in either color, $R(1,t)=R(s,1)=1$.
For $s,t\geq2$, splitting the neighbors of one <vertex> by the colors of their incident <edges> gives
$$
R(s,t)\leq R(s-1,t)+R(s,t-1).
$$
Indeed, in a <complete graph> of the order on the right, at least $R(s-1,t)$ neighbors are joined to that <vertex> by red <edges>, or at least $R(s,t-1)$ are joined by blue <edges>. In the red case, the defining property of the smaller <Ramsey number> supplies either a blue $t$-<clique> among the neighbors or a red $(s-1)$-<clique> that extends by the chosen <vertex>; the blue case is symmetric. Starting from the one-<vertex> base cases, this recursively proves finite existence. The <binomial upper bound for a Ramsey number> packages the resulting estimate. https://www.its.caltech.edu/~dconlon/RamseyLecture1.pdf[David Conlon's Graph Ramsey Theory notes, Lecture 1]{ref} present the neighbor argument and the sharp <Ramsey number for triangles>.
Equivalently, every <graph> on at least $R(s,t)$ <vertices> has an $s$-<clique> or a $t$-element <independent set>: color its <edges> red and the <edges> of its <complement graph> blue. This is the <Ramsey theorem> in <graph theory>. Larger monochromatic patterns have their own thresholds, such as a <graph Ramsey number>, <matching Ramsey number> or <triangle-packing Ramsey number>; these ask different questions from finding one <clique>.
Back to article page
