Compter les colorations de la grille qui évitent certaines fonctionnalités

Une coloration d'une grille m × $k$$m \times n$ est une fonction . Un rectangle brisé en C est un tuple ( i , i ′ , j , j ′ ) satisfaisant C ( i , j ) = C ( i ′ , j ) = C $C:[m] \times [n] \to [k]$$C$$(i,i',j,j')$ - c'est-à-dire que les trois coins du rectangle sont exactement de la même couleur.$C(i,j) = C(i',j) = C(i,j') \ne C(i',j')$

Je m'intéresse à la question suivante:

En fonction de , combien existe-t-il de couleurs k (pour les grilles de toute taille) qui évitent les lignes en double, les colonnes en double et les rectangles cassés?$k$$k$

Jusqu'à présent, je sais que la réponse est finie, et la meilleure borne supérieure que je peux prouver est (voir ci-dessous).$k^{(1.5 k!)^2}$

Je soulignerai également qu'il s'agit d'une question différente de celle dont Gasarch a souvent parlé sur son blog (et dans cet article ). Il veut éviter tous les rectangles monochromes, alors que cela ne me dérange pas, ce sont juste les "cassés" que je veux éviter.

Quelle est la motivation? En cryptographie, nous considérons le problème d'Alice (qui a ) et de Bob (qui a y ) apprenant tous les deux f ( x , y ) pour une fonction convenue f , de telle sorte qu'ils n'apprennent pas plus que f ( x , y ) . Vous pouvez associer f naturellement à un tableau à 2 dimensions, donc une coloration de grille. Il existe des caractérisations pour ce type de problème de la forme suivante (mais avec une notation différente): " f a une propriété intéressante sur le plan cryptographique si et seulement si $x$$y$$f(x,y)$$f$$f(x,y)$$f$$f$$f$contient un rectangle cassé. "Pour des exemples, voir Kilian91 et BeimelMalkinMicali99 .

Donc, ce problème est survenu dans un cadre de cryptographie que j'étudiais. Pour mes besoins, il suffisait de savoir qu'il existe un nombre fini de colorations de grille qui évitent les rectangles cassés et les lignes / colonnes en double. Mais j'ai pensé que le problème combinatoire lui-même est intéressant et je pense que de meilleures limites devraient être possibles.

La meilleure borne que je peux prouver: Définissez et R ( k ) = k ⋅ R ( k - 1 ) ; d'où R ( k ) = 1,5 k ! . Tout d'abord, on peut prouver que si C est une coloration k avec au moins R ( k $R(2)=3$$R(k) = k \cdot R(k-1)$$R(k) = 1.5 k!$$C$$k$$R(k)$lignes, puis il a soit une ligne en double ou un rectangle cassé. Symétriquement, on peut montrer la même chose en ce qui concerne les colonnes. (La preuve est assez basique, suivant le principe du pigeonnier sur le nombre de couleurs.) De cela, nous savons que les colorations qui nous intéressent ont toutes des dimensions plus petites que , et nous pouvons obtenir un limite supérieure très lâche de k R ( k ) 2 telles colorations.$R(k) \times R(k)$$k^{R(k)^2}$

Je pense que cela peut être amélioré de deux manières: Premièrement, je pense que la valeur optimale de est de 2 k - 1 + 1 . Vous trouverez ci-dessous une famille de colorants (définis de manière récursive), où C k est un k- coloriage de taille 2 k - 1 × 2 k - 1 qui évite ces caractéristiques interdites:$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].$

Je pense que ce sont les plus grandes couleurs qui évitent ces structures interdites.$k$

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

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

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