Minimum amount of colors preventing an equilateral uniformly colored subtriangle

In the Bundeswettberweb Infomatik 2010/2011, there was an interesting problem:

For fixed $n$, find a minimal $k$ and a map $\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$, such that there is no triple $(i,j),(i+l,j),(i+l,j+l)$ with $\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l)$.

Namely we are looking for the minimal amount of colors for a triangle, such that there is no uniformly colored equilateral subtriangle (the following picture shows an invalid coloring as the highlighted vertices form such an uniformly colored equilateral subtriangle):

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$ In fact they asked for a reasonably small $k$ for $n=1000$ and in the solution (written in german) they noted that a greedy approach yields a coloring with $27$ colors for $n=1000$, which can be reduced to $15$ by randomizing colors until a valid solution is found.

I am interested into exact solutions (for smaller $n$). The solution says that backtracking yields that $2$ colors are sufficient for $n\in\{2,3,4\}$ and $3$ are sufficient for $5\leq n \leq 17$, where backtracking is already really slow for $n=17$.

First I tried to use an ILP formulation and Gurobi to get some results for $n>17$, but it was too slow (already for $n=17$). Then I used a SAT solver, because I noticed that there is a straight forward formulation as a SAT-instance.

With that approach I was able to generate a solution with $3$ colors for $n=18$ within $10$ minutes:

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$ But to decide if $3$ colors suffice for $n=19$ it is already too slow. Is there some different approach that gives exact solutions for $n \geq 19$? Certainly we can't expect a polynomial algorithm.

• interesting question. why do you say we can't expect a polynomial time algorithm? Jan 22 '14 at 19:50
• @SashoNikolov it is just an assumption because this seems to be harder than finding a valid vertex coloring (harder in terms of more constraints), and vertex coloring is already a very hard problem. Jan 22 '14 at 20:04

Just an extended comment:

You can take a look to the approach used by Steinbach and Posthoff to find the 4-coloring of a 18x18 (and 12x21) grid without monochromatic rectangles:

Bernd Steinbach and Christian Posthoff, Solution of the Last Open Four-Colored Rectangle-free Grid an Extremely Complex Multiple-Valued Problem. In Proceedings of the 2013 IEEE 43rd International Symposium on Multiple-Valued Logic (ISMVL '13)

As proved by Gasarch et al. given a partial $c$-coloring of an arbitrary $n \times m$ rectangle, it is NP-complete to decide if the coloring can be extended to the whole rectangle without monochromatic rectangles: Daniel Apon, William Gasarch, Kevin Lawler, An NP-Complete Problem in Grid Coloring. So there are high chances that the problem is NP-complete even for equilateral triangles .... I think it would be a nice result to prove it.

Just a side note: I spent weeks of CPU cycles on the monochromatic rectangle-free 4-coloring problem but I started from a wrong partial result (a wrong previous analysis that restricted the number of possible 1-color sub-configurations) and I used the STP constraint solver; you can achieve great improvements if you add constraints that break symmetries (e.g. an ordering on the coloring of a side of the triangle) and try to make an analysis of the possible configurations using only 1-color.

EDIT: this is the result of an STP program for n=19 (~ 1 min.) • Thank you for the solution of $n=19$. I tried it myself in the meantime and wrote a little STP program ( pastebin.com/efzHu5md ). Unfortunately it is not really faster than the direct SAT approach, I thus assume that it is possible to choose the inequalities better than I did. Feb 13 '14 at 17:15

Using a SAT-based approach, I can confirm every instance is 3-colorable up to $n \leq 22$. A local search solver finds a solution for $n=22$ still rather quickly on a modern desktop. I tried the same approach for $n=23$, but obtained no solution in about 96 hours. It is thus tempting to conjecture that $n=23$ is not 3-colorable anymore. (Let me also remark that a 4-coloring is found instantly for $n=23$).

My observation for $n=19$ was similar to yours, that is, it already seems quite out of reach for a complete solver if the straightforward encoding is used. On the other hand, I wouldn't be surprised if a smarter encoding could settle the case of $n=23$ (and beyond?).

Below is the solution for $n=22$. Many thanks to Marzio for generating the image, and for letting me know about the problem! :-)
{"ft_lang_label":"__label__en","ft_lang_prob":0.9179266,"math_prob":0.97957104,"size":1682,"snap":"2022-05-2022-21","text_gpt3_token_len":450,"char_repetition_ratio":0.14541121,"word_repetition_ratio":0.0076923077,"special_character_ratio":0.30856124,"punctuation_ratio":0.103343464,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9971935,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,5,null,5,null,5,null,5,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-01-22T17:42:29Z\",\"WARC-Record-ID\":\"<urn:uuid:04b5d257-1b8c-4d07-8323-95b7017c94ce>\",\"Content-Length\":\"148846\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e827665a-bcad-4318-8f3a-336c04507af8>\",\"WARC-Concurrent-To\":\"<urn:uuid:6d1049d7-0e6e-47b3-b485-c848d9931170>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://cstheory.stackexchange.com/questions/20687/minimum-amount-of-colors-preventing-an-equilateral-uniformly-colored-subtriangle/20691#20691\",\"WARC-Payload-Digest\":\"sha1:ZUDNAK3HPETTQCKLXG4MKIA7GYBOXT7V\",\"WARC-Block-Digest\":\"sha1:EAKVS5YME7JAB72AFJRD5EYPUD7PRH4W\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-05/CC-MAIN-2022-05_segments_1642320303868.98_warc_CC-MAIN-20220122164421-20220122194421-00387.warc.gz\"}"}