[Math] Verify that R(p,2) = R(2,p) = p, where R is the Ramsey number

combinatoricsgraph theoryramsey-theory

Verify that $R(p,2) = R(2,p) = p$, where $R$ is the Ramsey number

It just seems obvious that $R(p,2) = R(2,p)$.

But why do $R(p,2)$ and $R(2,p)$ both equal p?

Best Answer

$R(2,p)=p$ because either all of the edge choices $\{x,y\}$ are colored $1$, or there are some $2$ elements $x_0,y_0\in V$ such that $\chi(\{x_0,y_0\})=2$. Remember, a choice of two vertices is a choice of an edge.

To expand a bit: $R(2,p)$ is the smallest number such that the complete graph on $R(2,p)$ nodes has a complete subgraph on $p$ nodes or $2$ nodes. Now, if all the edges are colored $1$ (i.e. the first color) then we have a complete subgraph on $p$ nodes and clearly $R(2,p)\ge p$. If not, then at least one edge is colored with the second color, i.e. $2$. However an edge is EXACTLY a copy of a complete graph on $2$ nodes. If we have at least $p$ nodes, then assuming even one single edge is not colored $1$, we have an edge (i.e. a complete 2-subgraph) of color $2$ guaranteed.

Related Question