Ramsey Theory

Theorem (Bichromatic K6 has Monochromatic K3)

Given any coloring of the edges of a Complete Graph $K_6$ with two colors, there is always a monochromatic $K_3$ subgraph.

Proof:

Select any vertex $v\in K_6$, and suppose our two colors were red and blue. Since $\mathrm{deg}(v)=5$ and there are two colors, by the Pidgeonhole Principle, either $v$ has $3$ red edges or blue edges. Suppose it has $3$, such that $a,b,c$ are the incident vertices of those red edges.

If there is a red edge between any two of $a,b,c$ then we have $K_3$. If not, then $a,b,c$ must have blue edges between them, which forms $K_3$.

Therefore we have a monochromatic $K_3$ in either case.

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzpicture}[\n vertex/.style={circle, draw, fill=white, inner sep=2pt, font=\\small},\n red_edge/.style={red, thick},\n blue_edge/.style={blue, thick},\n highlight_red_edge/.style={red, ultra thick},\n node distance=2cm,\n every node/.style={font=\\small}\n]\n\n$

source code

Ramsey’s Theorem

For any positive integers $p,q$, there $\exists N$ so that for any $n\ge N$ and any red-blue coloring of the edges of a complete graph $K_n$, there is either a red $K_p$ or a blue $K_q$.

In particular, we defined the smallest such number $N$ as the Ramsey Number, $R(p,q)$.

Proof:

We proceed by induction on $p+q$. If $p=1$ or $q=1$, then any coloring of a $K_1$ is red or blue. Indeed

$$R(1,q)=R(p,1)$$

Assume $R(p^{\prime },q^{\prime })$ is finite for all $p^{\prime }+q^{\prime }<p+q$. For $p,q>1$ we will show not only that $R(p,q)$ is finite, but that

$$(\ast )R(p,q)\le R(p-1,q)+R(p,q-1)$$

Take that

$$n\ge R(p-1,q)+R(p,q-1)$$

and color $K_n$. Consider vertex $v\in K_n$. Then

$${\mathrm{deg}}_{K_n}(v)=n-1\ge R(p-1,q)+R(p,q-1)-1$$

Indeed, $v$ has at least that many edges. By the Pidgeonhole Principle (recall this is the same technique we used in proving the previous theorem), either it has

• $R(p-1,q)$ red edges
• or $R(p,q-1)$ blue edges. WLOG, let $v$ have that many red many edges to the other vertices $S$.

graph LR;
	v((v)) o--o S[[S]];
	v o--o S;
	v o--o S;
	v o--o S;
	v o--o S;
	v o--o S;

To be more precise, + \omega(K_{p}

$$S=\{u\in N(v)|(u,v)\in E\text{ is colored red}\}$$

Thus, $|S|\ge R(p-1,q)$. This lets us apply the inductive hypothesis, such that either $S$ contains

• red $K_{p-1}$
  • In this case, we form $K_p=K_{p-1}\cup \{v\}$. Where $K_{p-1}$, the red Clique of $p$.
• blue $K_q$
  • We get blue $K_q$ Either way, we get our desired result.

Computing Ramsey Numbers

• $R(p,q)=R(q,p)$ by symmetry
• $R(1,n)=1$
• $R(2,n)=n$
  • any red edge gives red $K_2$
  • or we can color$K_n$ entirely blue
  • Consider $K_{n-1}$. We can have red $K_2$, but we cannot have blue $K_n$, so this is not a lower bound.
• $R(3,3)=6$.
  • We can show that $R(3,3)\le R(2,3)+R(3,2)=3+3=6$. This is due to $(\ast )$ in the proof of Ramsey’s Theorem.
  • To show it cannot be smaller, then we would need to show an invalid coloring on $K_5$. Indeed, the following is a coloring of $K_5$ where there is no $K_3$ red or blue.

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzpicture}[\n vertex/.style={circle, draw, fill=black, inner sep=2pt},\n red_edge/.style={red, thick},\n blue_edge/.style={blue!80!cyan, thick},\n node distance=2cm\n]\n\n$

source code

• $R(3,4)=9$
  • The upper bound is found by showing any red-blue coloring of a $K_9$ has either a red $K_3$ or blue $K_4$. We know that $R(3,3)+R(2,4)=6+4=10$. So, consider $K_9$.
  • Pick some $v\in K_9$. If $v$ has at least $4$ red $v\to S$ edges, then as $S$ is at least a $K_4$, if any internal edge is red, we have red $K_3$ (include $v$). If not, then all edges must be blue. But then we at least have a blue $K_4$, as desired.
  • If $v$ has at least $6$ blue $v\to S$ edges, then we apply the same logic. More importantly, since $R(3,3)=6$, then we are guaranteed to have red $K_3$ or blue $K_3$.
    • If red $K_3$ we are done.
    • If blue $K_3$, add $v$, giving us blue $K_4$ we are done.
    • Note that we can do the same for the previous case with $R(2,4)$.
  • Otherwise, each vertex must have $5$ blue and $3$ red edges.
  • However, this violates the Handshake Lemma. The total number of red edges is $(9\cdot 3)/2=13.5$, so any coloring of the graph means there must be at least one vertex of $6$ blue and $4$ edges.
• $R(4,4)=18$
  • We see that $R(4,4)\le R(3,4)+R(4,3)=9+9=18$. So it suffices to show that $R(4,4)>17$.
    • The lower bound requires to do some construction. In particular, we arrange $17$ vertices in a circle and d raw a red edge between two if they are separated by $1,2,4,8$ steps.
    • Leave the other edges blue, and symmetry makes this easy.
• The other known Ramsey Numbers. See here.

Theorem (Upper Bound On Ramsey Numbers)

$$R(p,q)\le 2^{p+q}$$

Proof: Induct on $p+q$. If $p=1$ or $q=1$, then $R(p,q)=1<2^{p+q}$. Now assume the inequality holds for smaller $p+q$. Then

$$\begin{array}{rl}R(p,q)& \le R(p-1,q)+R(p,q-1)\\ & \le 2^{p+q-1}+2^{p+q-1}\\ & \le 2^{p+q}\end{array}$$

and we are done.

Theorem (Lower Bound on Ramsey Numbers)

If $n\ge 3$, then $R(n,n)\ge 2^{n/2}$.

Proof:

We note that $R(p,q)\ge 2^{\min (p,q)/2}$. Combined with the upper bound, this says the symmetric Ramsey Numbers are exponentially large.

The key idea is to randomly color $K_N$. On average, how many chromatic $K_n$‘s are there in $K_N$? There are approximately $N^n$ many collections of $n$ vertices. Each has

$$\approx 2^{-n(n-1)/2}$$

probability of being monochromatic. So, the average is

$$\frac{N^n}{2^{n(n-1)/2}}\approx {\left[\frac{N}{2^{(n-1)/2}}\right]}^n$$

If $N$ is much smaller than $2^{n/2}$, then this is less than $1$, so some coloring must have none.

Definition (Graph Ramsey Number)

For graphs $G,H$, we define the graph Ramsey Number $R(G,H)$ to be the minimum $n$ so that any red-blue coloring of $K_n$ has either a red copy of $G$ or a blue copy of $H$.

Note that since $G,H$ are contained in complete graphs, then $R(G,H)$ is finite.

For example, $R(C_4,C_4)=6$. To prove the lower bound, we need to show any coloring of $K_5$ contains no monochromatic $C_4$. For the upper bound, one must show any $2-$edge coloring of $K_6$ has at least one monochromatic $C_4$.

Theorem (Graph Ramsey Number Upper Bound)

$$R(G,H)\le R(|V_G|,|V_H|)$$

Note that the RHS is shorthand for the Ramsey Number notation. It is equivalent to $R(K_{|V_G|},K_{|V_H|})$.

Proof:

Let $m=R(|V_G|,|V_H|)$. Any red-blue coloring of $K_m$ has either a monochromatic complete red graph on $|V_G|$ or monochromatic blue complete graph on $|V_H|$. These contain a red copy of $G$ or blue copy of $H$, by embedding $G$ in $K_{|V_G|}$ and likewise for $H$ and $K_{|V_H|}$.

Theorem (Graph Ramsey Number: Tree, Complete)

If $m,n$ are integers with $m-1$ dividing $n-1$ and $T_m$ is a Tree with $m$ vertices then

$$R(T_m,K_{1,n})=m+n-1$$

Proof:

We first want to find a lower bound. In particular, we want to color $K_{m+n-2}$ without a red $T_m$ or blue $K_{1,n}$. Note the that

$$m+n-2=(m-1)+(n-1)⟹m-1\mid m+n-2$$

We color $K_{m+n-2}$ by partitioning it into red $K_{m-1}$ and connect them with blue edges.

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzpicture}\n$

source code

Indeed, we have no red $T_m$, since

• the only red edges are in $K_{m-1}$
• every vertex in a $K_{m-1}$ is in a Cycle and thus cannot be in a tree

Likewise, there are no blue complete bipartite graph $K_{1,n}$ (star graph with $n$ edges) since each vertex has at most a blue degree of

$$(m+n-3)-(m-2)=n-1$$

where there are $(m+n-3)$ other vertices, and $(m-2)$ other vertices in each red $K_{m-1}$, such that we can only make $n-1$ other blue edges. Because $n-1<n$, we cannot make $K_{1,n}$.

For the upper bound, we need to show that any red-blue coloring of a $K_{n+m-1}$ has either a red $T_m$ or a blue $K_{1,n}$. If any vertex has $n$ or more blue edges, we have a blue $K_{1,n}$. Otherwise, consider subgraph $G_r$, the graph of only red edges.

Let $v\in G_r$. Then as every vertex has less than $n$ blue edges,

$$\begin{array}{rl}{\mathrm{deg}}_{G_r}(v)& ={\mathrm{deg}}_{K_{n+m-1}}(v)-{\mathrm{deg}}_{\text{blue}}(v)\\ & \ge (n+m-2)-(n-1)\\ & =m-1\end{array}$$

Therefore $\delta (G_r)\ge m-1$ by construction.

Lemma: Let $T$ be any tree on $k$ vertices and $G$ a graph with $\delta (G)\ge k-1$. Then $G$ contains a copy of $T$.

The proof idea is to build on $T$ one vertex at a time form $G$. We proceed by induction on $k$. If $k=1$, then it is trivial to embed a single point. Assume we can embed any tree on $k-1$ vertices. Let $v$ be a leaf of $T$. Removing $v$ and its singular edge $(u,v)$ gives us $T^{\prime }$. By the inductive hypothesis, we can embed $T^{\prime }$ in $G$. We now need to add back $e$ by picking some $v^{\prime }\in G$ to represent $v$ (if we can do this, then we have embedded $T$ in $G$). Since $\delta (G)\ge k-1$ and $|V(T^{\prime })|=k-1$, then we have at minimum $(k-1)-(k-2)=1$ vertices not paired with $u$, indeed this is $v^{\prime }$, and by adding $(u,v^{\prime })$, this is our tree $T$ with $k$ vertices, and we are done.

Back to the proof, $\delta (G_r)\ge m-1$ implies that we have a red tree $T_m$, completing the theorem.