Contando cores da grade que evitam determinados recursos

A coloração de uma grade m × $k$$m \times n$ é uma função . Um retângulo quebrado em C é uma tupla ( i , i ' , j , j ' ) que satisfaz C ( i , j ) = C ( i ' , j ) = C $C:[m] \times [n] \to [k]$$C$$(i,i',j,j')$ - ou seja, exatamente três cantos do retângulo são da mesma cor.$C(i,j) = C(i',j) = C(i,j') \ne C(i',j')$

Estou interessado na seguinte pergunta:

Em função de , quantas cores k existem (para grades de qualquer tamanho) que evitam linhas duplicadas, colunas duplicadas e retângulos quebrados?$k$$k$

Até agora eu sei que a resposta é finita, e o melhor limite superior que posso provar é (veja abaixo).$k^{(1.5 k!)^2}$

Também vou apontar que essa é uma pergunta diferente da mencionada frequentemente por Gasarch em seu blog (e neste artigo ). Ele quer evitar todos os retângulos monocromáticos, enquanto eu não me importo com retângulos monocromáticos, são apenas os "quebrados" que eu quero evitar.

Qual é a motivação? Na criptografia, consideramos o problema de Alice (que tem ) e Bob (que tem y ) aprendendo f ( x , y ) para uma função acordada f , de tal forma que eles aprendem não mais que f ( x , y ) . Você pode associar f naturalmente a uma tabela bidimensional, portanto, uma coloração de grade. Existem caracterizações para esse tipo de problema da seguinte forma (mas com notação diferente): " f possui alguma propriedade criptograficamente interessante se e somente se $x$$y$$f(x,y)$$f$$f(x,y)$$f$$f$$f$contém um retângulo quebrado. "Para obter exemplos, consulte Kilian91 e BeimelMalkinMicali99 .

Portanto, esse problema surgiu em algum cenário de criptografia que eu estava investigando. Para meus propósitos, bastava saber que há um número finito de cores de grade que evitam retângulos quebrados e duplicam linhas / colunas. Mas pensei que o problema combinatório em si é interessante e acredito que limites melhores deveriam ser possíveis.

O melhor limite que posso provar: Defina e R ( k ) = k ⋅ R ( k - 1 ) ; portanto R ( k ) = 1,5 k ! . Primeiro, pode-se provar que se C é uma coloração k com pelo menos R ( k $R(2)=3$$R(k) = k \cdot R(k-1)$$R(k) = 1.5 k!$$C$$k$$R(k)$linhas, então ele tem uma linha duplicada ou um retângulo quebrado. Simetricamente, pode-se mostrar a mesma coisa com relação às colunas. (A prova é bastante básica, seguindo o princípio do buraco de pomba no número de cores.) A partir disso, sabemos que os corantes de que gostamos têm dimensões menores que , e podemos obter uma muito solto limite superior de k R ( k ) 2 tais corantes.$R(k) \times R(k)$$k^{R(k)^2}$

Eu acho que isso pode ser melhorado de duas maneiras: Primeiro, acho que o valor ótimo de é 2 k - 1 + 1 . Abaixo está uma família de cores (definida recursivamente), em que C k é uma cor k de tamanho 2 k - 1 × 2 k - 1 que evita esses recursos proibidos:$R(k)$$2^{k-1}+1$$C_k$$k$$2^{k-1} \times 2^{k-1}$

$\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].$

Acredito que essas sejam as maiores pinturas em que evitam essas estruturas proibidas.$k$

$R(k)$$k^{R(k)^2}$$R(k) \times R(k)$

$k$$k$$k^{mn}$

$\ge 1-2^{-100}$