Size of a $3$-colored square grid to produce a monochrome rectangle Given a square grid, dimension $k\times k$, how big does $k$ have to be so that a $3$-coloring  will always produce a monochrome rectangle - a set of some four same-colored points of the grid in a rectangle aligned to the grid axes?
(There will be a monochrome rectangle when, for some choice of $a,b,c,d\in \big[1,k\big]$ with $a\neq b$ and $c\neq d$, all the points $(a,c),(a,d),(b,c),(b,d)\,$ have the same color.)

This is a follow-on from Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle?, where a $3$-colored $4\times 19$ grid is shown to contain a monochrome rectangle, so we already know $k\le 19$.
My current work shows $k\le 12$ but I think the limit on $k$ can be smaller.
${\large k\le 12}$
For each column we have a number of grid points of each color present. These produce a number of pairs of matched colors. The minimum number of such pairs in a column in a $12\times 12$ grid is achieved when the count of different colors is $(4,4,4)$ giving $\binom 42+\binom 42+\binom 42=18$ pairs. Over $12$ columns we will have at least $12\times 18=216$ matched-color grid pairs. There are $\binom {12}{2} = 66$ possible pair positions and with a choice of $3$ colors $3\times 66= 198$ different color/pair combinations. Clearly with at least $216$ pairings in a $12\times 12$ $3$-colored grid there must be a color-matched pairing between columns and  hence a monochrome rectangle.

Can you improve on this limit?
 A: With $k=11$, your argument almost works, but can be saved: Each column has at least ${4\choose 2}+{4\choose 2}+{3\choose 2}=15$ monochrome pairs, thus there are at least $11\times 15=165$ monochrome pairs in all columns together. If any of the ${11\choose 2}=55$ row pairs contained more than three such pairs, we'd be done. As $55\cdot 3=165$, all bounds encountered must be sharp, that is:


*

*In each column, one colour occurs exactly three times and each of the other two colours occurs exactly six times

*Each of the $55$ row pairs contains exactly one monochrome pair of each colour


By the first bullet point, each colour contributes a multiple of three of pairs, contradicting the second bullet point.
A: Here is a $10 \times 10$ example with no monochrome rectangle, if my programming is correct:
$$\matrix{1 & 2 & 1 & 2 & 0 & 1 & 0 & 1 & 2 & 0\cr
2 & 1 & 0 & 2 & 2 & 0 & 0 & 1 & 0 & 1\cr
2 & 2 & 1 & 1 & 0 & 2 & 1 & 0 & 0 & 2\cr
2 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 1\cr
0 & 0 & 2 & 2 & 1 & 2 & 1 & 1 & 0 & 0\cr
2 & 0 & 2 & 1 & 1 & 0 & 2 & 0 & 1 & 1\cr
0 & 1 & 1 & 2 & 0 & 0 & 2 & 2 & 1 & 2\cr
0 & 1 & 2 & 0 & 1 & 1 & 0 & 0 & 2 & 2\cr
1 & 1 & 0 & 1 & 2 & 2 & 2 & 0 & 2 & 0\cr
1 & 2 & 2 & 0 & 2 & 0 & 1 & 2 & 1 & 0\cr
}$$
(color version:)

