Zählen von Rasterfarben, die bestimmte Merkmale vermeiden

Eine Färbung eines m × n- Gitters$k$$m \times n$ ist eine Funktion . Ein gebrochenes Rechteck in C ist ein Tupel ( i , i ' , j , j ' ) , das C ( i , j ) = C ( i ' , j ) = C ( erfüllt $C:[m] \times [n] \to [k]$$C$$(i,i',j,j')$ - das heißt, genau drei Ecken des Rechtecks ​​haben dieselbe Farbe.$C(i,j) = C(i',j) = C(i,j') \ne C(i',j')$

Ich interessiere mich für folgende Frage:

Wie viele k- Farben gibt es in Abhängigkeit von (für Gitter beliebiger Größe), die doppelte Zeilen, doppelte Spalten und unterbrochene Rechtecke vermeiden?$k$$k$

Bisher weiß ich, dass die Antwort endlich ist und die beste Obergrenze, die ich beweisen kann, (siehe unten).$k^{(1.5 k!)^2}$

Ich möchte auch nur darauf hinweisen, dass dies eine andere Frage ist als die, über die Gasarch in seinem Blog (und in diesem Artikel) häufig gesprochen hat . Er möchte alle monochromatischen Rechtecke vermeiden, während es mir nichts ausmacht, monochromatische Rechtecke zu verwenden, sondern nur die "gebrochenen", die ich vermeiden möchte.

Was ist die Motivation? In der Kryptographie betrachten wir das Problem, dass Alice (die ) und Bob (die y haben ) beide f ( x , y ) für eine vereinbarte Funktion f lernen, so dass sie nicht mehr als f ( x lernen , y ) . Sie können f natürlich mit einer zweidimensionalen Tabelle verknüpfen , daher eine Rasterfarbe. Es gibt Charakterisierungen für diese Art von Problem in der folgenden Form (jedoch mit unterschiedlicher Notation): " f hat genau dann eine kryptografisch interessante Eigenschaft, wenn $x$$y$$f(x,y)$$f$$f(x,y)$$f$$f$$f$enthält ein gebrochenes Rechteck. "Beispiele finden Sie unter Kilian91 und BeimelMalkinMicali99 .

Dieses Problem ist also in einer Kryptografieumgebung aufgetreten, die ich untersucht habe. Für meine Zwecke war es ausreichend zu wissen, dass es eine begrenzte Anzahl von Rasterfarben gibt, die gebrochene Rechtecke und doppelte Zeilen / Spalten vermeiden. Aber ich fand das kombinatorische Problem selbst interessant und ich glaube, dass bessere Grenzen möglich sein sollten.

Die beste Grenze, die ich beweisen kann: Definiere und R ( k ) = k ⋅ R ( k - 1 ) ; daher ist R ( k ) = 1,5 k ! . Erstens kann man beweisen, dass wenn C eine k- Färbung mit mindestens R ( k $R(2)=3$$R(k) = k \cdot R(k-1)$$R(k) = 1.5 k!$$C$$k$$R(k)$Zeilen, dann hat es entweder eine doppelte Zeile oder ein gebrochenes Rechteck. Symmetrisch kann man dasselbe in Bezug auf Spalten zeigen. (Der Beweis ist ziemlich einfach und folgt aus dem Pigeonhole-Prinzip für die Anzahl der Farben.) Daraus wissen wir, dass die Farben, die uns alle interessieren, Abmessungen haben, die kleiner als , und wir können a erhalten sehr lockere Obergrenze von k R ( k ) 2 solcher Färbungen.$R(k) \times R(k)$$k^{R(k)^2}$

Ich denke , dies kann auf zwei Arten verbessert werden: Erstens, ich glaube , der optimale Wert von ist 2 k - 1 + 1 . Nachfolgend finden Sie eine (rekursiv definierte) Familie von Färbungen, wobei C k eine k- Färbung der Größe 2 k - 1 × 2 k - 1 ist , die diese verbotenen Merkmale vermeidet:$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].$

Ich glaube, dass dies die größten Farben sind, die diese verbotenen Strukturen vermeiden.$k$

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

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

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