Ramsey Numbers¶

Familiarization¶

Bounds¶

Finding the exact value of \(R(a,b)\) is not possible, but bounds can be provided for it.

First, we must prove that \(R(a, b)\) exists. (It might be that for no \(n\) does \(K_n\) have the desired property).

The idea for the solution is to find a vertex that has enough blue or red neighbors, and then consider only the neighbors of that vertex to find a smaller blue or red clique there.

More precisely, suppose there exists a vertex \(u\) that has at least \(R(a-1,b)\) blue neighbors. In this case, if you consider the neighbors of this vertex, two scenarios arise:

• It contains a blue \(K_{a-1}\), in which case we can obtain a blue \(K_a\) by adding vertex \(u\) to it.

• It contains a red \(K_b\).

So, if there is a vertex with at least \(R(a-1,b)\) blue neighbors, the problem is solved. Similarly, if there is a vertex with at least \(R(a, b-1)\) red neighbors, the problem is also solved.

Therefore, we conclude that \(R(a,b) \leq R(a-1,b) + R(a,b-1)\) because if our graph has at least \(R(a-1,b) + R(a,b-1)\) vertices, any arbitrary vertex you consider will either have enough blue neighbors or enough red neighbors.

The inequality above reminds us of Pascal's identity. ( \(\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\) )

It can also be proven by induction that \(R(a, b) \leq \binom{a+b}{a}\)

Generalization to k dimensions¶

Imagine we have a set of \(n\) elements, and every \(k\)-subset of it is colored with either blue or red. Now, we call a subset like \(A\) a \(k\)-dimensional clique if all \(k\)-subsets of \(A\) are monochromatic (of the same color). (If this color is blue, we call it a blue clique, and if it's red, we call it a red clique).

Now we define \(R_k(a,b)\) as the minimum \(n\) such that any 2-coloring (blue and red) of its \(k\)-subsets contains either a blue \(a\)-clique or a red \(b\)-clique.

The proof idea is similar to the above. Assume \(n = R_k(a,b)\). Consider a specific element \(u\) from the \(n\)-element set \(A\). Let \(B = A - \{u\}\). We color each \((k-1)\)-subset of \(B\), say \(S\), with the color of the \(k\)-subset \(S \cup \{u\}\). If the number of elements in \(B\) is at least \(R_{k-1}( R_k(a-1,b), R_k(a,b-1) )\), then one of the following two events occurs:

• \(B\) contains a blue \((k-1)\)-dimensional clique, say \(S\), of size at least \(R_k(a-1,b)\). In this case, either \(S\) contains a red \(k\)-dimensional clique of size \(b\) (in which case the problem is solved). Or \(S\) contains a blue \(k\)-dimensional clique of size \(a-1\). In this case, we can add \(u\) to this set, and we have a \(k\)-dimensional blue clique of size \(a\).

• \(B\) contains a red \((k-1)\)-dimensional clique, say \(S\), of size at least \(R_k(a,b-1)\). In this case, either \(S\) contains a blue \(k\)-dimensional clique of size \(a\) (in which case the problem is solved). Or \(S\) contains a red \(k\)-dimensional clique of size \(b-1\). In this case, we can add \(u\) to this set, and we have a \(k\)-dimensional red clique of size \(b\).

According to the above, it can be proven that \(R_k(a,b) \leq R_{k-1}(R_k(a-1,b),R_k(a,b-1))\)

Generalization to k dimensions and c colors¶

Similarly, we can state and prove the problem for more than two colors. We leave finding bounds on \(R_k(a_1,a_2,...,a_c)\) to the reader.