What a Multicolor Ramsey Number Measures
Ramsey numbers ask when a complete graph becomes too large to color its edges while avoiding specified monochromatic cliques. With several colors, the targets can differ: one color might be required to contain a triangle, another a 4-clique, and a third a 5-clique. The tuple of target sizes records which clique is required in which color.
Throughout, the graphs are finite and simple. The complete graph \(K_n\) has \(n\) vertices and an edge between every pair of distinct vertices. Fix an integer \(m\ge 1\). An edge-coloring with \(m\) colors assigns to each edge exactly one label from \(\{1,\ldots,m\}\); a color is allowed not to occur. A clique is a set of pairwise adjacent vertices. A clique is monochromatic in color \(i\) if all its edges have color \(i\).
The condition is disjunctive: a coloring succeeds if it contains a clique meeting at least one of the listed color-specific targets. It need not contain all the target cliques. A coloring that avoids the required outcome must avoid a color-\(i\) clique of size \(s_i\) for every \(i\).
For the parameters \(s_i\ge2\), the finite Ramsey theorem guarantees that such an \(n\) exists. This is the standard existence result established in the earlier material on finite Ramsey numbers. Thus “least” is meaningful: among the positive integers with the forcing property, there is a smallest one.
The Two-Color Notation
When \(m=2\), call color 1 red and color 2 blue. Then \(R(s,t)\) is the standard shorthand for \(R(s,t)=R(s_1,s_2)\), where \(s_1=s\) and \(s_2=t\). It is the least \(n\) such that every red-blue coloring of the edges of \(K_n\) has either a red \(K_s\) or a blue \(K_t\). In particular, the targets are attached to colors: \(R(3,4)\) asks for a red triangle or a blue \(K_4\), not a monochromatic clique of either size in either color.
Proof. A two-coloring is an assignment of one of two labels to every edge. Rename the first label red and the second blue; this changes no edge assignments or cliques. By the multicolor definition, \(K_n\) is forcing precisely when every such assignment contains a color-1 \(K_s\) or a color-2 \(K_t\). After the renaming, this says every red-blue coloring contains a red \(K_s\) or a blue \(K_t\). Therefore the sets of positive integers \(n\) that satisfy the two definitions are identical, and their least elements are identical. \(\square\)
For example, the earlier exact result \(R(3,4)=9\) says that every red-blue coloring of \(K_9\) has a red triangle or a blue \(K_4\), while at least one red-blue coloring of \(K_8\) avoids both. Switching the color names gives \(R(4,3)=9\): the same statement with blue and red exchanged.
Two Basic Properties of the Notation
Proof. Let \(\pi\) be a permutation of \(\{1,\ldots,m\}\). Given any coloring, replace each edge color \(i\) by \(\pi(i)\). This is a bijection between the colorings before and after relabeling: applying the inverse permutation recovers the original coloring. A monochromatic \(K_{s_i}\) in color \(i\) becomes a monochromatic \(K_{s_i}\) in color \(\pi(i)\). Thus the forcing property for the target assigned to each color is unchanged when the color labels and their targets are permuted together. The same integers \(n\) are forcing before and after the relabeling, so their least values agree. For two colors, exchanging their labels exchanges \(s\) and \(t\), giving \(R(s,t)=R(t,s)\). \(\square\)
Proof. Put \(N=R(b_1,\ldots,b_m)\). Every \(m\)-coloring of \(K_N\) contains a monochromatic \(K_{b_i}\) in some color \(i\). Any \(a_i\) vertices of that clique form a monochromatic \(K_{a_i}\) in the same color, because every pair among those vertices is still joined by an edge of color \(i\). Hence every coloring of \(K_N\) also meets one of the smaller targets \(a_i\). So \(N\) has the forcing property for \((a_1,\ldots,a_m)\), and the least order with that property is at most \(N\). \(\square\)
These properties concern the meaning of the parameters, not a method for computing general multicolor values. In particular, the tuple is not an unordered list until the associated color labels are permuted as well.
Worked Examples
Worked Example: Reading \(R(3,3)\) as a Two-Color Number
The earlier exact result is \(R(3,3)=6\). Interpret the number and check the lower-bound coloring on five vertices.
For the lower-bound coloring, let \(V=\{1,2,3,4,5\}\). Color the edges in \(\{12,23,34,45,51\}\) red and those in \(\{13,14,24,25,35\}\) blue. These two sets are disjoint and together contain all \(\binom{5}{2}=10\) edges of \(K_5\). The red edges form the cycle \(1,2,3,4,5,1\), so contain no triangle. The blue edges form the cycle \(1,3,5,2,4,1\), so also contain no triangle. Thus this coloring avoids both a red \(K_3\) and a blue \(K_3\), showing that order 5 does not force the outcome.
At order 6, the exact result \(R(3,3)=6\) says every red-blue coloring contains a red triangle or a blue triangle. Together, the coloring on five vertices and the forcing result on six vertices verify the meaning of the least order: \(R(3,3)=6\).
Check: the lower coloring uses \(5+5=10\) edges, exactly the number in \(K_5\). Neither color class is a triangle, while the stated order-6 result supplies the upper bound. The two checks give \(5<6\) and the claimed least value.
Worked Example: A Color-Specific Target of Size Two
Find \(R(2,3,3)\). Color 1 requires only a monochromatic \(K_2\), which is a single edge; colors 2 and 3 each require a triangle.
For a lower-bound coloring on five vertices, take \(V=\{1,2,3,4,5\}\), use no edges of color 1, and color the edges \(\{12,23,34,45,51\}\) with color 2 and \(\{13,14,24,25,35\}\) with color 3. The two sets partition the ten edges of \(K_5\). As checked in the preceding example, each set forms a 5-cycle, so neither contains a triangle. Since color 1 has no edges, there is no color-1 \(K_2\) either. Therefore order 5 does not force any of the three targets.
Now consider any coloring of \(K_6\) with colors 1, 2 and 3. If at least one edge has color 1, its two endpoints form a color-1 \(K_2\). If no edge has color 1, the coloring uses only colors 2 and 3. The earlier result \(R(3,3)=6\) then guarantees a triangle in color 2 or in color 3. Thus every coloring of \(K_6\) meets a target, and the five-vertex coloring shows that \(R(2,3,3)=6\).
Check: color 1 is allowed to be unused in a coloring that avoids all targets. The lower example has ten edges split as five of color 2 and five of color 3; the upper argument covers both possibilities for color 1, so \(6\) is the least forcing order.
Worked Example: Two Targets of Size Two
Find \(R(2,2,5)\). The first two colors each force success as soon as a single edge receives that color; the third color requires a \(K_5\).
For order 4, let \(V=\{1,2,3,4\}\) and color all six edges \(\{12,13,14,23,24,34\}\) with color 3. There are no edges of colors 1 or 2, and four vertices cannot contain a \(K_5\). This coloring avoids every target, so \(R(2,2,5)>4\).
For order 5, take any coloring of \(K_5\). If an edge has color 1, its endpoints form a color-1 \(K_2\); if an edge has color 2, its endpoints form a color-2 \(K_2\). If neither color occurs, all \(\binom{5}{2}=10\) edges have color 3, and the five vertices form a color-3 \(K_5\). Hence every coloring of \(K_5\) meets a target, so \(R(2,2,5)=5\).
Check: \(K_4\) has \(\binom{4}{2}=4\cdot3/2=6\) edges, all accounted for in the lower coloring. At order 5, either one of the first two edge-colors appears or all ten edges are color 3; both cases force the required clique.
One-Color and Multi-Color Interpretations
The definition also has a simple one-color boundary case. If \(m=1\), then \(R(s_1)=s_1\): all edges have the only color, so \(K_{s_1}\) itself supplies the target at order \(s_1\), while a graph on fewer than \(s_1\) vertices cannot contain that many vertices. This illustrates the role of the order parameter: the number is the first order at which every coloring is forced, not the first order at which some coloring contains the clique.
For more colors, a coloring is a partition of the edges into color classes, and each class is tested against its own target size. Some classes can be empty. The example \(R(2,3,3)\) depends on this point: the lower-bound coloring deliberately leaves color 1 unused. Disallowing unused colors would change the definition and is not part of Ramsey coloring.
Common Pitfalls
Confusing a target tuple with one common clique size. In \(R(3,4)\), success means a red triangle or a blue \(K_4\), not any monochromatic clique of size 3 or 4. Always pair each coordinate \(s_i\) with its color \(i\).
Forgetting to prove both sides of an exact value. A coloring on \(n-1\) vertices that avoids all targets proves only \(R>n-1\). A separate argument must show that every coloring on \(n\) vertices succeeds. Conversely, proving that every coloring of \(K_n\) succeeds gives \(R\le n\), but does not rule out a smaller value.
Treating all colors as required to appear. The definition asks for a monochromatic clique in at least one of the assigned target colors. It does not require every color to occur. Lower-bound colorings often use only some of the available colors.
Check Your Understanding
For each question, keep track of both the clique size and the color to which it is assigned.
- In \(R(3,5)\), state precisely the two outcomes that make a red-blue coloring successful.
- Explain why a coloring of \(K_7\) avoiding a red \(K_4\) and a blue \(K_3\) proves \(R(4,3)>7\).
- Use the definition to prove \(R(s)=s\) for one color and \(s\ge2\).
- Why does relabeling colors preserve a Ramsey number only when the target sizes are relabeled with them?
- For \(R(2,4,4)\), explain why any color-1 edge immediately meets a target, and what must be shown if color 1 is absent.