Существование «раскрасочных матриц»

Изменить: теперь есть дополнительный вопрос, связанный с этим сообщением.

---

Определения

Позволять $c$ а также $k$быть целыми числами. Мы используем обозначения$[i] = \{1,2,...,i\}$,

$c \times c$ матрица $M = (m_{i,j})$ Говорят, что $c$-До-$k$раскраска, если выполнено следующее:

• у нас есть $m_{i,j} \in [k]$ для всех $i, j \in [c]$,
• для всех $i,j,\ell \in [c]$ с $i \ne j$ а также $j \ne \ell$ у нас есть $m_{i,j} \ne m_{j,\ell}$,

Мы пишем $c \leadsto k$если существует раскрасочная матрица to- .$c$$k$

---

Обратите внимание, что диагональные элементы не имеют значения; мы заинтересованы только в недиагональных элементах .$M$

Следующая альтернативная перспектива может быть полезной. Пусть - множество недиагональных элементов в строке , и аналогично пусть будет набором недиагональных элементов в столбце . Теперь является to- раскрашивающей матрицей, если для всех . То есть строка и column должны состоять из отдельных элементов (за исключением, конечно, по диагонали).$R(M,\ell) = \{ m_{\ell,i} : i \ne \ell \}$$\ell$$C(M,\ell) = \{ m_{i,\ell} : i \ne \ell \}$$\ell$$M$$c$$k$

$$R(M,\ell) \subseteq [k], \quad C(M,\ell) \subseteq [k], \quad R(M,\ell) \cap C(M,\ell) = \emptyset$$ $\ell \in [c]$$\ell$$\ell$

Может быть или не быть полезным попытаться интерпретировать как особый вид хэш-функции от до .$M$$[c]^2$$[k]$

Примеры

Вот матрица раскраски от до :$6$$4$

$$\begin{bmatrix} -&2&2&1&1&1\\ 3&-&3&1&1&1\\ 4&4&-&1&1&1\\ 3&2&2&-&3&2\\ 4&2&2&4&-&2\\ 3&4&3&4&3&- \end{bmatrix}.$$

В общем, известно, что для любого имеемНапример, и . Чтобы увидеть это, мы можем использовать следующую конструкцию (например, Naor & Stockmeyer 1995).$n \ge 2$

$${2n \choose n} \leadsto 2n.$$ $20 \leadsto 6$$6 \leadsto 4$

Пусть и . Пусть биекция из на множество всех -подмножеств из , то есть и для всех . Для каждого с выберите произвольно$c = {2n \choose n}$$k = 2n$$f$$[c]$$n$$[2n]$$f(i) \subseteq [2n]$$|f(i)| = n$$i$$i,j \in [c]$$i \ne j$

$$m_{i,j} \in f(i) \setminus f(j).$$

Обратите внимание, что . Нетрудно убедиться, что конструкция действительно является раскрашивающей матрицей; в частности, мы имеем и .$f(j) \setminus f(i) \ne \emptyset$$R(M,\ell) = f(\ell)$$C(M,\ell) = [k] \setminus f(\ell)$

Вопрос

Оптимальная конструкция выше? Иными словами, есть ли у нас для любого ?

$${2n \choose n} + 1 \leadsto 2n$$ $n \ge 2$

Хорошо известно, что указанная конструкция асимптотически жесткая; обязательно . Это следует, например, из результата Линиала (1992) или прямого применения теории Рамси. Но мне неясно, является ли конструкция также плотной до постоянных. Некоторые численные эксперименты показывают, что приведенная выше конструкция может быть оптимальной.$k = \Omega(\log c)$

мотивация

Вопрос связан с существованием быстрых распределенных алгоритмов раскраски графов. Например, предположим, что нам дано направленное дерево (все ребра ориентированы к корневому узлу), и предположим, что нам дана правильная окраска дерева. В настоящее время существует распределенный алгоритм , который вычисляет правильную окраски дерева в синхронной связи раунда , если и только если .$c$$k$$1$$c \leadsto k$

Конструкция является оптимальной в том смысле, что не может выполняться. Действительно, легко видеть, что раскрашивающая матрица c- to- k существует тогда и только тогда, когда существуют c подмножества A ₁ ,…, A _c множества {1,…, k }, такие, что никакие различные i и j не удовлетворяют A _я ⊆ _J . (Для направления «только если», возьмите A _i = R ( M , i ) для c- to- k раскраски матрицы$\binom{2n}{n}+1 \leadsto n$M, Для направления «если» установите m _ij ∈ A _i ∖ A _j .) Семейство множеств, ни одно из которых не содержит другого, называется семейством Спернера , и по теореме Спернера максимальное число множеств в семействе Спернеров на размер вселенной k равен . Это означает, что .$\binom{k}{\lfloor k/2\rfloor}$$c \leadsto k \iff c \le \binom{k}{\lfloor k/2\rfloor}$

Для немного более жесткой асимптотики можно доказать, что:

если , то$c \leadsto k$$c \leq 2^k$

Предположим, что существует раскраска матрицы с использованием цветов. Теперь раскрасьте каждую строку в матрице набором цветов, которые она содержит. Это дает раскраску строк с использованием подмножеств . Разные строки должны иметь разные цвета. В противном случае предположим, что для строка$c \times c$$k$$[k]$$i \lt j$$i$ имеет тот же цвет, что и строка$j$, Это означает, что цвет$(i,j)$ присутствует в обоих рядах $j$ и в столбце $j$что противоречит тому, что мы начали с раскраски. Это следует из того$c \leq 2^k$