3 Colorings of graphs and Ramsey’s theorem

Chromatic Number

Definition

A proper coloring of a graph $G$ is a function from the vertices to a set $C$ of ‘colors’ (e.g. $C=\{1,2,3,4\}$) such that the ends of every edge have distinct colors. If $|C|=k$, we say that $G$ is $k$-colored.

The chromatic number $\chi (G)$ of a graph $G$ is the minimal number of colors for which a proper coloring exists.

If $\chi (G)=2$, then $G$ is called bipartite. A graph with no odd polygons (equivalently, no closed paths of odd length) is bipartite as the reader should verify.

Brooks

Let $d⩾3$ and let $G$ be a graph in which all vertices have degree $⩽d$ and such that $K_{d+1}$ is not a subgraph of $G$. Then $\chi (G)⩽d$.

\begin{proof} See A course in combinatorics - 1992 - van Lint, Wilson.pdf, page 24. \end{proof}

Ramsey Theory on Graphs

Problem

Can we have a party with $6$ people such that no $3$ know each other and no $3$ do not know each other?

Definition

Define $R(s,t)$ as the smallest integer $n$ such that all (edge)-colorings with $2$ colors $\{c_1,c_2\}$ of $K_n$ contain a monochromatic $K_s$ in color $c_1$ or a monochromatic $K_t$ in color $c_2$. It also equals the smallest integer $n$ such that all graphs $G$ on $n$ vertices satisfy

• $K_s$ is a subgraph of $G$;
• $K_t$ is a subgraph of $\overline{G}$.

For example, $R(3,3)=6$, $R(2,t)=R(t,2)=t$.

Proposition

$R(s,t)⩽R(s-1,t)+R(s,t-1)$.

\begin{proof} Consider a graph $G$ on $n$ vertices without $K_s$ in $G$ and without $K_t$ in $\overline{G}$. Let $x$ be a vertex. Then $N(x)$ cannot contain any $K_{s-1}$ and so $|N(x)|⩽R(s-1,t)-1$. Also $\overline{N}(x)$ cannot contain any $K_{t-1}$ and so $|\overline{N}(x)|⩽R(s,t-1)-1$.

Hence $R(s,t)-1⩽|\{x\}|+|N(x)|+|\overline{N}(x)|⩽1+R(s-1,t)-1+R(s,t-1)-1$. Now we finish the proof. \end{proof}

Corollary

$R(r,s)⩽\left(\genfrac{}{}{0ex}{}{r+s-2}{r-1}\right)$.

\begin{proof} Note that $R(1,s)=R(r,1)=1$. Then by ^b25753 and by induction. \end{proof}

Definition

Define $R(r;m):=R(r_1,\cdots ,r_m)$ with $r=r_1=\cdots =r_m$ for $m$ colors.

Diagonal Ramsey Numbers

Theorem

$C\cdot 2^{s/2}⩽R(s,s)⩽D\cdot 4^{s-1}$.

• $C$: Erdos, 1947
• $D$: Erdos, Szekeres, 1935

Remark. In 2024, $R(s,s)⩽(4-ϵ{)}^s$, see here. In 2025, an improvement lower bound of $R(s,cs)$, see here.

\begin{proof} By ^bxbn9o and Stirling’s formula,

$$R(s,s)⩽\left(\genfrac{}{}{0ex}{}{2s-2}{s-1}\right)=\frac{(2s-2)!}{((s-1)!{)}^2}$$

we finish the proof of upper bound.

For the lower bound, consider a $K_n$. There are $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ different ways of coloring the edges red or blue. Now fix a subgraph $K_p$. There are $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)-\left(\genfrac{}{}{0ex}{}{p}{2}\right)+1}$ colorings for which that $K_p$ is monochromatic.

The number of colorings for which some $K_p$ is monochromatic is at most $\left(\genfrac{}{}{0ex}{}{n}{p}\right)$ times as large (because we may count some colorings more than once). If this number is less than the total number of colorings, then there exist colorings with no monochromatic $K_p$. Using the fact that $\left(\genfrac{}{}{0ex}{}{n}{p}\right)<n^p/p!$, we find that such a coloring certainly exists if $n<2^{p/2}$ (unless $p=2$ ).

This proves the following theorem. \end{proof}

Off-diagonal Ramsey Numbers

Reference table for off-diagonal Ramsey bounds (compiled by lyh).

Ramsey Theory on Structures and Spaces

Schur's theorem

Let $n$ be a positive integer, and let $s_n$ be the smallest integer such that $[s_n]$ colored in $n$ colors has monochromatic $x+y=z$. Such $s_n$ exists.

\begin{proof} We identify that $n$ colors with $[n]$. Define a coloring $K_{s_n}$ with $V(K_{s_n})=[n]$ with $uv$ in color $x\in [n]$ if $|u-v|$ has color $x$.

If $s_n⩾R(3,\cdots ,3)=R(n;3)$, then we find a monochromatic $K_3$. That is, $|v-u|$, $|v-w|$, $|u-w|$ is monochromatic. WLOG assume $u>v>w$ and put $x=u-v$, $y=v-w$ and $z=u-w$. Then $x+y=z$. \end{proof}

Definition

Define $[q{]}^n:=\{(x_1,\cdots ,x_n):x_i\in [q]\}$. We say $L\subseteq [q{]}^n$ is a combinatorial line if there exists $I\subseteq [n]$ and integers $a_i$ such that

$$L=\{(x_1,\cdots ,x_n)\in [q{]}^n:x_i=a_i\text{ for }i\notin I\text{ and }{x}_i=x_j\text{ for all }i,j\in I\}.$$

Hales-Jewett

For all $r,q\in {\mathbb{N}}_{+}$, there exists smallest $n:=HJ(r,q)$ such that any $r$-coloring of $[q{]}^n$ contains a monochromatic combinatorial line.

\begin{proof} By induction on $q$. The case of $q=1$ is trivial, and we now assume that $q⩾2$.

For a line $L$, we write $L^{-}$ for its first point and $L^{+}$ for its last point. We call $L_1,\cdots ,L_s$ focused at $f$ if $L^{+}=f$ for all $i\in [s]$. We call $L_1,\cdots ,L_s$ color-focused at $f$ if all the truncated lines are monochromatic and of pairwise different colors. Note that a line is determined by one point and a “direction”.

Suppose that $HJ(r,q^{\prime })$ is finite for all $q^{\prime }⩽q-1$. Our goal is, for each $s⩽r$, show there exists $N=FHJ(r,s,q)$ such that any $r$-coloring of $[q{]}^N$ either

• contains a monochromatic combinatorial line, or
• contains $s$ color-focused lines.

Then $r=s$ will show the Hales-Jewett theorem by the pigeonhole principle.

Now we prove our goal by induction on $s$: When $s=1$, pick $FHJ(r,1,q)=HJ(r,q-1)$. Now suppose that $FHJ(r,s^{\prime },q)$ is finite for all $s^{\prime }⩽s-1$. We claim that

$$FHJ(r,s,q)⩽N=FHJ(r,s-1,q)+HJ(r^{q^n},q-1)=:n+n^{\prime }.$$

Suppose $x$ is $r$-coloring $[q{]}^N$, where $[q{]}^N=\{(a_1,\cdots ,a_{n^{\prime }},\cdots ,a_N):a_i\in [q]\}$. Then we can write $(a_1,\cdots ,a_n,\cdots ,a_N)$ as $(a,b)$, where $a=(a_1,\cdots ,a_n)$ and $b=(a_{n+1},\cdots ,a_N)$. So $x$ can be identified as an $r^{q^n}$-coloring $[q{]}^{n^{\prime }}$, by associating each point $b\in [q{]}^{n^{\prime }}$ with the entire $r$-colored cube $\{(a,b):a\in [q{]}^n\}$. For each $b\in [q{]}^{n^{\prime }}$, its color in $x^{\prime }$ is $x^{\prime }(b)$, which is indeed a function $f_b:[q{]}^n\to [r],a\mapsto x(a,b)$.

Since $n^{\prime }=HJ(r^{q^n},q-1)$, there exists a line $L$ with coordinate set $I^{\prime }$ such that $L\setminus \{L^{+}\}$ is monochromatic under $x^{\prime }$. For any $b,b^{\prime }\in L\setminus \{L^{+}\}$, we have $x^{\prime }(b)=x^{\prime }(b^{\prime })$, i.e. $f_b=f_{b^{\prime }}$ for all $a\in [q^n]$. Define $x^{\prime \prime }(a):=x((a,b))=x((a,b^{\prime }))$ for all $a\in [q{]}^n$, then we get a $r$-coloring $x^{\prime \prime }$ on $[q{]}^n$.

Since $n=FHJ(r,s-1,q)$, either $[q{]}^n$ under $x^{\prime \prime }$ contains a monochromatic combinatorial line, or it contains $s-1$ color focused lines. If the former holds, then we already get a monochromatic combinatorial line in $[q{]}^N$ under $x$ and we have done. We now assume the latter holds, that is, there exists $s-1$ lines $L_1,\cdots ,L_{s-1}$ in $[q{]}^n$ which are color-focused at $f$. Then define $L_1^{\prime },\cdots ,L_s^{\prime }$ as follows:

• for $1⩽i⩽s-1$, define $L_i^{\prime }$ in $[q{]}^N$ with first point $(L_i^{-},L^{-})$ and active coordinates $I_i\cup I^{\prime }$,
• for $i=s$, define $L_s^{\prime }$ with first point $(f,L^{-})$ and active coordinates $I^{\prime }$,

where

• $I_i\subseteq \{1,\dots ,n\}$ is the set of active coordinates for the line $L_i$ in the subspace $[q{]}^n$, that is, for any $j\in I_i$, the $j$-th coordinate of points in $L_i$ varies synchronously from 1 to $q$,
• $I^{\prime }\subseteq \left\{n+1,\dots ,n+n^{\prime }\right\}$ is the set of active coordinates for the line $L$ in the subspace $[q{]}^{n^{\prime }}$.

It is easy to check that these lines $L_i^{\prime }$ are color-focused with focus $(f,L^{+})$. Now we finish the proof. \end{proof}