For positive integers $a_1,\dots,a_n$, recall that the *multicolor Ramsey number* $R(a_1,\dots,a_n)$ is the smallest integer $N$ such that if the edges of the complete graph $K_N$ are colored with the $n$ colors $1,\dots,n$, then there is some $i\le n$ and a set of $a_i$ vertices, all of whose edges received color $i$.

A *maximal Ramsey$(a_1,\dots,a_n)$-coloring* is a witnessing $n$-coloring of $K_M$, where $M=R(a_1,\dots,a_n)-1$, that is, a coloring of the edges of $K_M$ with colors $1,\dots,n$ such that for no $i$ there is a copy of $K_{a_i}$ with all edges of color $i$.

By the way, is there a standard name for these objects? For $n=2$ they are sometimes called maximal Ramsey$(a_1,a_2)$-graphs (identifying one of the colors with a subgraph of $K_M$ and the other with its complement), but perhaps there is a nicer name. The name critical is also used, but the word is used as well with another meaning.

My question is the following:

Given $a_1,\dots,a_n$, let $L=R(a_2,\dots,a_n)-1$. Does every maximal Ramsey$(a_1,\dots,a_n)$-coloring have the property that we can find $L$ vertices none of whose edges received color 1?

For example, this holds for $n=2$. For instance, $R(4,4)=18$, and any 2-coloring of $K_{17}$ avoiding monochromatic copies of $K_4$ must have monochromatic triangles of each color.

It also holds for maximal Ramsey$(3,3,3)$-colorings. Here, $R(3,3,3)=17$ and in any 3-coloring of $K_{16}$ avoiding monochromatic triangles, for any of the colors we can find copies of $K_5$ where only the other two colors are used. (Recall that $R(3,3)=6$.)

I don't know if the property also holds for maximal Ramsey$(3,3,4)$-colorings, but I know it holds for the 3-coloring witnessing $R(3,3,4)>29$ described in J. G. Kalbfleisch's thesis (*Chromatic Graphs and Ramsey’s Theorem*, U. Waterloo, 1966). (Recall that $R(3,3,4)=30$.) Indeed, this coloring of $K_{29}$ admits a copy of $K_8$ avoiding the first color, a copy of $K_8$ avoiding the second color, and a copy of $K_5$ avoiding the third one. (Recall that $R(3,4)=9$.)

onemaximal coloring with such a large set, for any $(a_1,\ldots,a_n)$ ? $\endgroup$2more comments