Counting grid colorings that avoid certain features

Question

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.

Answer 1

If you want bounds for a fixed $k$ (rather than an asymptotic expression/formula that works for all $k$), one approach might be to use random sampling: repeatedly choose a random coloring, check whether it meets your criteria, and count how many of the trials were successful. This gives you an estimate of the fraction of colorings that meet your criteria. This can be converted into a rough estimate of the total number of colors that meet your criteria (just multiply by $k^{mn}$).

You can then use a Chernoff bound to get upper and lower bounds on the number of colorings that meet your criteria, where these bounds hold with probability $\ge 1-2^{-100}$ (taken over the random trials). In other words, you would have to be extremely unlucky in your choice of random trials for those bounds to be wrong.