Ramsey numbers

Perhaps made famous by the work of Erdős, the Ramsey numbers are one very nice example of graph theory and combinatorics.

Notation here is somewhat nasty (well, it could be worse), so say that a complete graph of size {n} is denoted as {K_n}, a totally disconnected graph as {D_n} (i.e. a graph with {n} vertices and {0} edges), and given a graph {G} the expression {K_n \leq G } means {G} has a subgraph with {n} vertices which is isomorphic to a complete graph (same for {D_n}).

Definition 1 Given {k,l\in\mathbb{N}}, the Ramsey number {R(k,l)} is the minimum number such that a graph with at least {R(k,l)} vertices either contains a subgraph isomorphic to {K_k} or to {D_l}.

In order to generalize this notion readily, it’s better to reformulate it in terms of {2}-colorings:

Definition 2 Given {k,l\in\mathbb{N}}, the Ramsey number {R(k,l)} is the minimum number such that any {2}-coloring of {K_{R(k,l)}} has a red subgraph isomorphic to {K_k} or a blue subgraph isomorphic to {K_l}.

In this way the definition only requires notation for complete subgraphs. Notice that the definition makes the Ramsey number naturally symmetric, {R(k,l)=R(l,k)}, that trivially {R(1,k)=1} for every {k} and {R(2,k)=k}. Finally, notice that the number is increasing in the arguments, i.e. {R(k,l)\leq R(k+1,l)}.

Anyway, this is a combinatorial frame, and in order to make sure the definition isn’t talking about the empty set we need to prove such numbers always exist. Here is the proof. Proof: We actually prove the inequality

\displaystyle R(s,t)\leq R(s-1,t)+R(s,t-1).

Pick {N\geq R(s-1,t)+R(s,t-1)} and consider any {2}-coloring of {K_N}. Every vertex has connectivity {N}, therefore either there is a vertex with at least {R(s-1,t)} outgoing red edges, or a vertex with {R(s,t-1)} outgoing blue edges (actually, every vertex falls in at least one of the two cases). The argument is of course completely symmetric, so suppose {v} is a vertex with {R(s-1,t)} outgoing red edges, and call {S} the set of vertices connected to {v} by a red edge. Then, by definition of {R(s-1,t)}, the complete graph on {S} either contains a red {K_{s-1}} red subgraph or a {K_l} blue subgraph. In the latter case we have nothing to add since we are already satisfied, in the former case consider {K_{s-1}\cup \{v\}}: this is a complete subgraph of size {s} with only red edges, thus isomorphic to {K_s}. \Box

The first possible generalization of Ramsey numbers is to higher colorings of graphs. One has naturally

Definition 3 Given {k} colors, {R_k(l_1,\ldots,l_k)} is the minimum number such that any {k}-coloring of {K_{R_k(l_1,\ldots,l_k)}} contains a color-1 subgraph isomorphic to {K_{l_1}}, or a color-2 subgraph isomorphic to {K_{l_2}}, {\ldots}, or a color-{k} subgraph isomorphic to {K_{l_k}}.

Again, we need to make sure these numbers exist. One actually sees how the previous proof generalizes to this case, and actually that there are a lot of different proofs of the same fact.

Notice: an edge of colour {j} is called a {j}-edge. A (sub)graph {K_l} with all {j}-edges is called a {j}-monochromatic complete (sub)graph.

Proof: It’s again true that if one of the arguments {l} is {1} then the number is identically {1}, and that the definition of {R_k} is symmetric in the arguments. Pick {N\geq R_k(l_1-1,\l_2,\ldots,l_k)+R_k(l_1,\l_2-1,\ldots,l_k)+\ldots+R_k(l_1,\l_2,\ldots,l_k-1)} and consider any {k}-coloring of {K_N}. Then there exists at least one vertex {v} and a color {j} such that {v} has at least {R_k(l_1,\ldots,l_j-1,\ldots,l_k)} outgoing {j}-edges. Call {S} the set of vertices connected to {v} by a {j}-edge. This is a subgraph of size {R_k(l_1,\ldots,l_j-1,\ldots,l_k)}, therefore if it doesn’t contain any monochromatic subgraph isomorphic to some {K_{l_i}} for {i\neq j} – in which case we are done – it contains a subgraph isomorphic to a {j}-monochromatic {K_{l_j-1}}, thus {K_{l_j-1}\cup \{v\}} is isomorphic to a {j}-monochromatic {K_{l_j}}. Notice we proved

\displaystyle R_k(l_1,\l_2,\ldots,l_k)\leq R_k(l_1-1,\l_2,\ldots,l_k)+\ldots+R_k(l_1,\l_2,\ldots,l_k-1) \ \ \ \ \ (1)

Another proof can be the following, based on what we could call “a dog vision argument”: collapse all colours {\{1,\ldots, k-1\}} into a single grey colour. Then pick {N\geq R(R_{k-1}(l_1,\ldots,l_{k-1}),l_k)} and consider a {2}-coloring of {K_N}. By the definition of Ramsey numbers, this graph either contains a {k}-monochromatic subgraph isomorphic to {K_{l_k}} or a grey-monochromatic subgraph isomorphic to {K_{R_{k-1}(l_1,\ldots,l_{k-1})}}. But then any {(k-1)}-coloring of this subgraph induces any {k}-coloring on {K_N}, and contains a monochromatic subgraph isomorphic to one of the {K_{l}}. Thus we have proven inequality

\displaystyle R_k(l_1,\l_2,\ldots,l_k)\leq R(R_{k-1}(l_1,\ldots,l_{k-1}),l_k) \ \ \ \ \ (2)

and the existence is proved by induction on the number of colours.

Another dog-vision proof in the same spirit could be, for {k} even, to prove the inequality

\displaystyle R_{k}(l_1,\ldots,l_{k}) \leq R_{\frac{k}{2}}(R(l_1,l_2),\ldots,R(l_{k-1},l_k)),

and so on with any combination of colors that can induce any {k}-coloring on {K_N} for {N} big enough, or inequality

\displaystyle R_k(l_1,\l_2,\ldots,l_k)\leq R_{k-1}(R(l_1,l_2),l_3,\ldots,l_k). \ \ \ \ \ (3)

\Box

If we look deeper into the recursions given by these inequalities we can find some upperbounds for the Ramsey numbers. In the {k=2} case, any quantity whose {(1,k)} terms are uniformly bounded is bounded by a constant times a binomial coefficient; in this case

\displaystyle R(k,l)\leq \binom{k+l-2}{k-1},

and Stirling approximation for {\binom{n}{n/2}} is {\sim \frac{2^{n+1}}{\sqrt{2\pi n}}}, that gives us the upperbound

\displaystyle R(k,k)\lesssim \frac{4^k}{\sqrt{k}}.

The following is instead an exponential LOWERbound on {R(k,k)}:

Proposition 4 {R(k,k)\geq 2^{\frac{k}{2}-1}}.

Proof: This is an example of probabilistic proof (which is just a counting argument in disguise).

Let {N} be an integer to be chosen later. Assume all the possible 2-colorings of {K_N} are equally likely, that is the probability distribution on the 3-colorings is uniform. We can realize this distribution by assigning to an edge color Red or Blue with probability {\frac{1}{2}}. The set of {2}-colorings is denoted by {\Omega} and a single coloring by {\omega}. We can think of these as functions on the edges. We want to prove

\displaystyle \Pr\left(\{\omega : \omega \mbox{ is a 3-coloring without monochromatic } K_k { subgraphs}\}\right)>0,

because that would imply we can avoid the situation which is realized in {K_{R(k,k)}}, that is {N < R(k,k)}.

Of course it is the same to prove that the probability of having a monochromatic {K_k} subgraph is strictly less than 1. Fix a subset of the vertices {S\subset V} of cardinality {k}, {|S|=k}, and denote by {\overline{S}} the edges of the (complete) subgraph with vertices {S}. Then the probability that {\overline{S}} is monochromatic is

\displaystyle \Pr\left(\{\omega\in\Omega\,:\, \omega\left(\overline{S}\right)=\{\mbox{Red}\}\mbox{ or }\{\mbox{Blue}\}\}\right) = 2 \left(\frac{1}{2}\right)^{\binom{|S|}{2}}\sim 2^{1-\frac{k^2}{2}}

because each edge has independent probability of {1/2} of being Red, and the number of edges is {\binom{|S|}{2}=\binom{k}{2}\sim k^2/2}. Thus the probability of having a monochromatic subgraph of size {k} is bounded by the sum of this probability over all possible subsets of size {k}, that is

\displaystyle \Pr\left(\{\omega\,:\, \mbox{coloring } \omega \mbox{ has a monochromatic subgraph of size } k\}\right)\leq 2\binom{N}{k} \left(\frac{1}{2}\right)^{\binom{|S|}{2}},

and this last term can be bounded by {\lesssim \frac{N^k 2^{1-\frac{k^2}{2}}}{k!}}. If we choose {N\lesssim 2^{\frac{k}{2}}} then the bound becomes {\lesssim \frac{1}{k!}}, which is {o(1)} and thus can be made smaller than one at most by limiting {N} by a further constant {<1}. \Box

The above argument is readily generalized to the case of {k} colours, giving the (polynomial in the colours, exponential in the size of the subgraphs) lowerbound

\displaystyle R_k(l,l,\ldots,l)\gtrsim k^{\frac{l}{2}-1}.

For {2} colours this is

\displaystyle 2^{\frac{k}{2}}\lesssim R(k,k) \lesssim \frac{4^k}{\sqrt{k}},

and notice that the diagonal value majorizes the Ramsey numbers for lower entries.

Let’s now look at some bounds depending on the colours. For example, we can prove

\displaystyle R_k(3,\ldots,3) \leq 3 k!

by using inequalities (1) and (3) combined: first

\displaystyle R_k(3,\ldots,3)\leq k R_k(2,3,\ldots,3)

because of (1) and the symmetry, then by (3)

\displaystyle R_k(2,3,\ldots,3)\leq R_{k-1}(R(2,3),3,\ldots,3)=R_{k-1}(3,3,\ldots,3)

because {R(2,3)=3}. Thus the claim is proven by induction on {k}, since {R(3,3)=6}. We can also prove a better lowerbound than the one found by the probabilistic argument, namely that

\displaystyle R_k(3,\ldots,3)\geq 2^k

i.e. the growth is at least exponential (the previous bound gave only {\gtrsim k^{1/2}}). To prove this, we argue by induction. If {k} is {2} then {R(3,3)=6>2^2}. Now, suppose it’s true for {k-1} and take a bipartite graph with {2^k} vertices. For each of the two partitions, colour the edges with {k-1} colours avoiding any triangle, which you can do by inductive hypothesis since they have size {2^{k-1}}. Then colour all the edges connecting the two partitions with the remaining colour: these edges form no triangles. The argument generalizes easily to prove

\displaystyle R_k(l,\ldots,l)\geq (l-1)^k.

For example, for {l=4}, take a tripartite graph of size {3^k}, colour each partition (of size {3^{k-1}}) with {k-1} colours avoiding every monochromatic {K_4} subgraph, then colour the edges connecting the partitions with the remaining colour. These edges form no {K_4}. So the claim is proven once we verify the basic case, which is {R(l,l)>(l-1)^2}. By the probabilistic lowerbound {R(l,l)>2^{l/2-1}}, and {2^{l/2-1}>(l-1)^2} is true for {l} big enough, so that our claim is certainly verified for at least big {l} (well, actually {l>17}, which is not so bad. Anyway, for {2<l<10} the claim is verified as well, look at this page of wikipedia for a summary of mixed methods results.).

Now we move on to see some applications of the Ramsey theory.

Theorem 5 (Schur) For {N} big enough, any {k}-coloring of the numbers {\{1,\ldots, N\}} is such that there exist {x,y} such that {x,y,x+y} have the same colour.

Proof: A colouring of the numbers can induce a coloring of a graph as follows. For the complete graph {K_N} and a coloring {c:\{1,\ldots,N\}\rightarrow \{1,\ldots,k\}} of the vertices, we induce a {k}-coloring of the graph by painting edge {(i,j)} in colour {c(|i-j|)}. Then choose {N \geq R_k(3,\ldots,3)}: there exists a monochromatic triangle then, with vertices {i < j < k}. This says that {c(j-i)=c(k-j)=c(k-i)}. Now, observe that if {x=j-i} and {y=k-j}, then {x+y=k-i}, that is, {c(x)=c(y)=c(x+y)}. \Box

Then every mechanism that induces colorings on the numbers actually induces colorings of graphs, and therefore one can find such triplets {(x,y,x+y)}. This has an unexpected and pleasant consequence:

Theorem 6 (Fermat’s theorem {\pmod{p}}) For every {m\in\mathbb{N}} and prime number {p} big enough, Fermat’s modular equation

\displaystyle x^m+y^m=z^m \pmod{p}

has at least one non trivial solution.

Proof: {\mathbb{Z}_p^{\times}} is a cyclic group, call {g} a generator and parametrize the {p-1} elements as {g^{mk+i}}, where {0\leq i \leq m-1}. Then choose as {m}-coloring the one given by {c(g^{mk+i})=i}. By Schur’s theorem, provided {p} is big enough, there exist {x,y\in \mathbb{Z}_p^{\times}} such that {c(x)=c(y)=c(x+y)=i}. That means the elements are of the form {x=g^{mk+i}, y=g^{mj+i}, x+y=g^{ml+i}}, and {g^{mk+i}+g^{mj+i}=g^{ml+i}\pmod{p}}. Dividing by {g^{i}} and taking {a=g^k, b=g^j, c=g^l} we have {a^m+b^m=c^m \pmod{p}}. \Box

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s