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

  • $\begingroup$ 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 $\endgroup$ Oct 26 '21 at 22:53
  • $\begingroup$ 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. $\endgroup$ Oct 26 '21 at 22:56
  • $\begingroup$ Hi @bof. No, $L$ is not a typo, I think the examples help clarify the notation. I made the suggested edit. $\endgroup$ Oct 26 '21 at 23:00
  • $\begingroup$ @Thomas Thanks for the remarks! $\endgroup$ Oct 26 '21 at 23:02
  • $\begingroup$ @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)$ ? $\endgroup$ Oct 26 '21 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.