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! :-)