Multicolor Triangle Ramsey Numbers

Take six people. Any two of them are friends or strangers. Then some three are all friends, or some three are all strangers. This always happens, and the reason is short.

Pick one person, Ann. Of the other five, at least three are friends of Ann, or at least three are strangers to Ann. Suppose that three are friends. If any two of them are friends with each other, those two and Ann are three friends. If not, those three are all strangers to each other. The other case works the same way.

With five people this can fail, as the figure shows. Draw the people as points and each pair as a line. Color the line by friends or strangers. The outer pentagon is one color and the star is the other, and neither color has a triangle.

Five points and two colors with no one-color triangle.

So 6 is the smallest number of points that forces a one-color triangle with 2 colors. In general, the Ramsey number $R_{k} (3)$ is the smallest number of points that forces a one-color triangle with $k$ colors. Thus $R_{2} (3) = 6$ and $R_{3} (3) = 17$ . Exact values are very hard, and $R_{4} (3)$ is only known to lie between 51 and 62.

The question is how fast this number grows as the colors increase. The argument above extends to more colors, and it gives an upper limit of about $2.7 \times k!$ , where $k! = 1 \times 2 \times \dots \times k$ . The best lower limit was about ${3.28}^{k}$ , which multiplies by a fixed amount for each new color. These two limits grow at very different speeds:

Colors $k$	Lower limit, about	Upper limit, about
10	$1.4 \times 10^{5}$	$9.9 \times 10^{6}$
20	$2.1 \times 10^{10}$	$6.6 \times 10^{18}$
30	$3.0 \times 10^{15}$	$7.2 \times 10^{32}$

Erdős offered $100 to decide if $R_{k} (3)$ grows like $c^{k}$ , for some fixed number $c$ . The lower limits came from combining colorings. Take two colorings with no one-color triangle, on $N$ points with $k$ colors and on $M$ points with $ℓ$ colors. They combine into such a coloring on $N M$ points with $k + ℓ$ colors. For example, the five-point coloring combines with itself to give 25 points with 4 colors. Repeating this only gives growth like $c^{k}$ .

OpenAI reports a different construction, built in stages, that grows faster. For a fixed number $c$ above 0 and every $k$ from 2 up:

R_{k} (3) \geq {(\frac{c k^{1 / 3}}{\log k})}^{k}

Here $k^{1 / 3}$ is the cube root of $k$ , and $\log k$ is the logarithm of $k$ , which grows with the number of digits of $k$ . The cube root grows much faster, so the number inside the brackets grows with $k$ , and the growth beats $c^{k}$ for every fixed $c$ . This answers Erdős's question. Both limits now grow roughly like $k$ raised to a multiple of $k$ . A later paper extends the method from triangles to other odd cycles, which are closed loops with an odd number of lines.