Подсчет цветов сетки, которые избегают определенных функций

-раскраске с т × п сетки$k$$m \times n$ является функция . Сломан прямоугольник в C является кортежем ( я , я ' , J , J ' ) , удовлетворяющие С ( я , J ) = С ( я ' , J ) = С $C:[m] \times [n] \to [k]$$C$$(i,i',j,j')$ - то есть ровно три угла прямоугольника одного цвета.$C(i,j) = C(i',j) = C(i,j') \ne C(i',j')$

Меня интересует следующий вопрос:

В зависимости от , сколько существует k- цветов (для сеток любого размера), которые избегают дублирования строк, дублирования столбцов и разбитых прямоугольников?$k$$k$

Пока я знаю, что ответ конечен, и лучшая верхняя оценка, которую я могу доказать, это (см. Ниже).$k^{(1.5 k!)^2}$

Я также просто укажу, что это другой вопрос, чем тот, о котором Гасарч часто говорил в своем блоге (и в этой статье ). Он хочет избежать всех монохроматических прямоугольников, в то время как я не возражаю против монохроматических прямоугольников, это просто «разбитые», которых я хочу избежать.

Какова мотивация? В криптографии мы рассматриваем проблему Алисы (у которой есть ) и Боба (у которой есть y ), которые изучают f ( x , y ) для согласованной функции f таким образом, что они учатся не более чем f ( x). , у ) . Вы можете ассоциировать f естественно с 2-мерной таблицей, следовательно, раскраской сетки. Существуют характеристики для такого рода задач следующего вида (но с другими обозначениями): « f обладает некоторым криптографически интересным свойством тогда и только тогда, когда $x$$y$$f(x,y)$$f$$f(x,y)$$f$$f$$f$содержит сломанный прямоугольник. "Например, см. Kilian91 и BeimelMalkinMicali99 .

Так что эта проблема возникла в какой-то криптографической установке, которую я исследовал. Для моих целей было достаточно знать, что существует конечное количество раскрасок сетки, которые избегают разбитых прямоугольников и дублирующих строк / столбцов. Но я думал, что сама комбинаторная проблема интересна, и я считаю, что лучшие границы должны быть возможны.

Лучшая оценка, которую я могу доказать: определим и R ( k ) = k ⋅ R ( k - 1 ) ; следовательно, R ( k ) = 1,5 k ! , Во-первых, можно доказать, что если C является k- раскраской с хотя бы R ( k $R(2)=3$$R(k) = k \cdot R(k-1)$$R(k) = 1.5 k!$$C$$k$$R(k)$ряды, то он либо имеет повторяющуюся строку или разбитый прямоугольник. Симметрично можно показать то же самое в отношении столбцов. (Доказательство довольно простое, исходя из принципа «квадратного отверстия» о количестве цветов.) Из этого мы знаем, что все цвета, которые нас интересуют, имеют размеры, меньшие чем , и мы можем получить очень рыхлая верхняя граница k R ( k ) 2 таких раскрасок.$R(k) \times R(k)$$k^{R(k)^2}$

Я думаю, что это можно улучшить двумя способами: во- первых, я думаю, что оптимальное значение составляет 2 k - 1 + 1 . Ниже приведено (рекурсивно определенное) семейство раскрасок, где C k - это k- раскраска размером 2 k - 1 × 2 k - 1, которая позволяет избежать этих запрещенных признаков:$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].$

Я считаю, что это самые большие раскраски, которые избегают этих запрещенных структур.$k$

Во-вторых , даже если бы можно было улучшить оценку для описанную выше, у нас все еще есть тот факт, что k R ( k ) 2 является очень грубой оценкой для общего числа раскрасок. Это учитывает все возможные цвета сетки R ( k ) × R ( k ) , большая часть которых предположительно имеет запрещенные признаки.$R(k)$$k^{R(k)^2}$$R(k) \times R(k)$

Если вам нужны границы для фиксированного (а не асимптотическое выражение / формула, которая работает для всех k ), один из подходов может заключаться в использовании случайной выборки: повторно выбирайте случайную раскраску, проверяйте, соответствует ли она вашим критериям, и подсчитайте, сколько из испытания были успешными. Это дает вам оценку доли окраски, которые соответствуют вашим критериям. Это может быть преобразовано в приблизительную оценку общего количества цветов, которые соответствуют вашим критериям (просто умножьте на k m n ).$k$$k$$k^{mn}$

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