A $k$-coloring of an $m \times n$ grid is a function $C:[m] \times [n] \to [k]$. A broken rectangle in $C$ is a tuple $(i,i',j,j')$ satisfying $C(i,j) = C(i',j) = C(i,j') \ne C(i',j')$ -- that is, exactly three corners of the rectangle are the same color.I'm interested in the following question:As a function of $k$, how many $k$-colorings exist (for grids of any size) that avoid duplicate rows, duplicate columns, and broken rectangles?So far I know that the answer is finite, and the best upper bound I can prove is $k^{(1.5 k!)^2}$ (see below).I'll also just point out that this is a different question than the one talked about by Gasarch frequently on his blog (and in this paper). He wants to avoid all monochromatic rectangles, whereas I don't mind monochromatic rectangles, it's just the broken ones that I want to avoid.What is the motivation? In cryptography, we consider the problem of Alice (who has $x$) and Bob (who has $y$) both learning $f(x,y)$ for an agreed-upon function $f$, in such a way that they learn no more than $f(x,y)$. You can associate $f$ naturally with a 2-dimensional table, hence, a grid coloring. There are characterizations for this kind of problem of the following form (but with different notation): $f$ has some cryptographically interesting property if and only if $f$ contains a broken rectangle. For examples, see Kilian91 and BeimelMalkinMicali99.So this problem has come up in some setting of cryptography that I was investigating. For my purposes, it was enough to know that there are a finite number of grid colorings that avoid broken rectangles and duplicate rows/columns. But I thought the combinatorial problem itself is interesting and I believe better bounds should be possible.The best bound I can prove: Define $R(2)=3$ and $R(k) = k \cdot R(k-1)$; hence $R(k) = 1.5 k!$. First, one can prove that if $C$ is a $k$ coloring with at least $R(k)$ rows, then it either has a duplicate row or a broken rectangle. Symmetrically, one can show the same thing with respect to columns. (The proof is pretty basic, following from the pigeonhole principle on the # of colors.) From this, we know that the colorings we care about all have dimensions smaller than $R(k) \times R(k)$, and we can get a very loose upper bound of $k^{R(k)^2}$ such colorings.I think this can be improved in two ways: First, I think the optimal value of $R(k)$ is $2^{k-1}+1$. Below is a (recursively defined) family of colorings, where $C_k$ is a $k$-coloring of size $2^{k-1} \times 2^{k-1}$ that avoids these forbidden features:$     \qquad     C_1 = [1];        \qquad     C_k = \left[ \begin{array}{ccc|ccc}                k & \cdots & k & \\                \vdots & \ddots & \vdots &  & C_{k-1} \\                k & \cdots & k & \\                    \hline                 & & & k & \cdots & k \\                 & C_{k-1} & & \vdots & \ddots & \vdots \\                 & & & k & \cdots & k            \end{array} \right].$I believe these to be the largest $k$-colorings that avoid these forbidden structures.Second, even if one could improve the bound on $R(k)$ described above, we still have the fact that $k^{R(k)^2}$ is a very coarse bound for the total number of colorings. This counts all possible $R(k) \times R(k)$ grid colorings, of which a large portion presumably have the forbidden features.
Counting grid colorings that avoid certain features
co.combinatorics