Liczenie kolorów siatki, które unikają pewnych funkcji

-coloring o siatka jest funkcją . Uszkodzony prostokąt w jest krotką spełniającą - to znaczy dokładnie trzy rogi prostokąta są tego samego koloru.m × $k$$m \times n$$C:[m] \times [n] \to [k]$( i , i ′ , j , j ′ ) C ( i , j ) = C ( i ′ , j ) = C ( i , j ′ ) ≠ C ( i ′ , j ′$C$$(i,i',j,j')$$C(i,j) = C(i',j) = C(i,j') \ne C(i',j')$

Interesuje mnie następujące pytanie:

W zależności od , ile istnieje kolorów- (dla siatek dowolnego rozmiaru), które unikają duplikatów wierszy, duplikatów kolumn i połamanych prostokątów?$k$$k$

Jak dotąd wiem, że odpowiedź jest skończona, a najlepszą górną granicą, jaką mogę udowodnić, jest (patrz poniżej).$k^{(1.5 k!)^2}$

Zwrócę też uwagę, że jest to inne pytanie niż to, o którym Gasarch często mówił na swoim blogu (i w tym artykule ). Chce unikać wszystkich monochromatycznych prostokątów, podczas gdy nie mam nic przeciwko monochromatycznym prostokątom, to tylko te „zepsute”, których chcę uniknąć.

Jaka jest motywacja? W kryptografii rozważamy problem Alicji (która ma ) i Boba (który ma ) uczących się dla uzgodnionej funkcji , w taki sposób, że uczą się nie więcej niż . Można skojarzyć naturalnie z tabeli 2-wymiarowe, a więc barwnik siatki. Istnieją charakterystyki dla tego rodzaju problemu o następującej formie (ale z inną notacją): „ ma jakąś kryptograficznie interesującą właściwość wtedy i tylko wtedy, gdy zawiera łamany prostokąt”. Przykłady podano w Kilian91 i BeimelMalkinMicali99 .y f ( x , y ) f f ( x , y ) f f $x$$y$$f(x,y)$$f$$f(x,y)$$f$$f$$f$

Więc ten problem pojawił się w niektórych ustawieniach kryptografii, które badałem. Dla moich celów wystarczyło wiedzieć, że istnieje skończona liczba kolorów siatki, które pozwalają uniknąć połamanych prostokątów i zduplikowanych wierszy / kolumn. Ale myślałem, że sam problem kombinatoryczny jest interesujący i uważam, że lepsze granice powinny być możliwe.

Najlepsza granica, jaką mogę udowodnić: Zdefiniuj i ; stąd. Po pierwsze, można udowodnić, że jeśli jest zabarwiającym z co najmniej rzędami, to albo ma zduplikowany rząd lub łamany prostokąt. Symetrycznie można pokazać to samo w odniesieniu do kolumn. (Dowód jest dość prosty, wynikający z zasady szuflady na # kolorów.) Z tego wiemy, że kolory, o które dbamy, mają wymiary mniejsze niż , i możemy uzyskać bardzo luźna górna granica takich kolorów.R ( k ) = k ⋅ R ( k - 1 ) R ( k ) = 1,5 k ! C k R ( k ) R ( k ) × R ( k ) k R ( k ) $R(2)=3$$R(k) = k \cdot R(k-1)$$R(k) = 1.5 k!$$C$$k$$R(k)$$R(k) \times R(k)$$k^{R(k)^2}$

Myślę, że można to poprawić na dwa sposoby: Po pierwsze, uważam, że optymalna wartość wynosi . Poniżej znajduje się (zdefiniowana rekurencyjnie) rodzina kolorystyczna, w której to kolorowanie o rozmiarze które pozwala uniknąć tych zabronionych funkcji:2 k - 1 + 1 C k k 2 k - 1 × 2 k - $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].$

Uważam, że są to największe kolory, które unikają tych zakazanych struktur.$k$

Po drugie , nawet jeśli można poprawić ograniczenie opisane powyżej, nadal mamy fakt, że jest bardzo grubą granicą dla całkowitej liczby zabarwień. Zlicza to wszystkie możliwe kolory siatki , z których duża część prawdopodobnie ma zabronione cechy.k R ( k ) 2 R ( k ) × R ( k $R(k)$$k^{R(k)^2}$$R(k) \times R(k)$

Jeśli potrzebujesz granic dla ustalonego (zamiast asymptotycznego wyrażenia / formuły, która działa dla wszystkich ), jednym z podejść może być losowe próbkowanie: wielokrotnie wybierz losowe zabarwienie, sprawdź, czy spełnia twoje kryteria i policz, ile próby zakończyły się powodzeniem. To daje oszacowanie frakcji barw, które spełniają twoje kryteria. Można to przeliczyć na przybliżoną całkowitą liczbę kolorów spełniających podane kryteria (wystarczy pomnożyć przez ).k k m $k$$k$$k^{mn}$

Następnie możesz użyć granicy Chernoffa, aby uzyskać górną i dolną granicę liczby kolorów, które spełniają twoje kryteria, przy czym te granice zachowują się z prawdopodobieństwem (przejęte przez losowe próby). Innymi słowy, musielibyście mieć pecha przy wyborze losowych prób, aby granice były błędne.$\ge 1-2^{-100}$