# On the structure of maximal Ramsey colorings

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$$.)

• My intuition would be "no" : I agree that the graph induced on $K_N$ by the colors $2,\ldots,n$ must be very close to be Ramsey for $(K_{a_2},\ldots, K_{a_n})$, but there are such graphs with small clique number (actually with max clique of size $K_{a_n}$ given a result by Folkman.). So I would expect that you might find "maximal coloring" without such set of vertices Oct 26 '21 at 22:53
• Note that I would personally write the problem in term of independence number : If $G_1,\ldots, G_n$ are the graphs induced by a maximal coloring (sometime referred as a color Pattern of $K_M$), your question ask for the minimum independence number of $G_1$, over all maximum coloring. I find it this formulation easier to generalize. Oct 26 '21 at 22:56
• Hi @bof. No, $L$ is not a typo, I think the examples help clarify the notation. I made the suggested edit. Oct 26 '21 at 23:00
• @Thomas Thanks for the remarks! Oct 26 '21 at 23:02
• @AndrésE.Caicedo, do we even know if we can find one maximal coloring with such a large set, for any $(a_1,\ldots,a_n)$ ? Oct 26 '21 at 23:03