Istnienie „matryc do barwienia”

Edycja: teraz jest pytanie uzupełniające związane z tym postem.

---

Definicje

Niech i będą liczbami całkowitymi. Używamy notacji .$c$$k$$[i] = \{1,2,...,i\}$

macierzy mówi się -to- barwiących matrycy , jeśli zachodzi:$c \times c$$M = (m_{i,j})$$c$$k$

• mamy dla wszystkich ,$m_{i,j} \in [k]$$i, j \in [c]$
• dla wszystkich z i mamy .$i,j,\ell \in [c]$$i \ne j$$j \ne \ell$$m_{i,j} \ne m_{j,\ell}$

Piszemy jeśli istnieje matryca barwiąca c - to - k .$c \leadsto k$$c$$k$

---

Zauważ, że elementy ukośne nie mają znaczenia; Jesteśmy zainteresowani tylko w non-ukośnych elementów $M$ .

Pomocna może być następująca perspektywa alternatywna. Niech $R(M,\ell) = \{ m_{\ell,i} : i \ne \ell \}$ będzie zbiorem elementów nie przekątnych w rzędzie $\ell$ , i podobnie niech $C(M,\ell) = \{ m_{i,\ell} : i \ne \ell \}$ będzie zbiorem elementów niediagonalnych w kolumnie $\ell$ . Teraz $M$ jest macierzą kolorów $c$ -to- $k$ iff

$$R(M,\ell) \subseteq [k], \quad C(M,\ell) \subseteq [k], \quad R(M,\ell) \cap C(M,\ell) = \emptyset$$ dla wszystkich $\ell \in [c]$ . Oznacza to, że wiersz $\ell$ i kolumna $\ell$ muszą składać się z odrębnych elementów (z wyjątkiem oczywiście na przekątnej).

Pomocna może być interpretacja jako specjalnego rodzaju funkcji skrótu od do .$M$$[c]^2$$[k]$

Przykłady

Oto macierz kolorowania -do- :$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}.$$

Ogólnie wiadomo, że dla każdego mamyNa przykład i . Aby to zobaczyć, możemy użyć następującej konstrukcji (np. Naor i Stockmeyer 1995).$n \ge 2$

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

Niech i niech . Niech będzie bijectionem z do zbioru wszystkich podzbiorów , to znaczy i dla wszystkich . Dla każdego z wybierz dowolnie$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).$$

Zauważ, że . Łatwo jest zweryfikować, czy konstrukcja rzeczywiście jest matrycą koloryzującą; w szczególności mamy i .$f(j) \setminus f(i) \ne \emptyset$$R(M,\ell) = f(\ell)$$C(M,\ell) = [k] \setminus f(\ell)$

Pytanie

Czy powyższa konstrukcja jest optymalna? Innymi słowy, czy mamy dla dowolnego ?

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

Dobrze wiadomo, że powyższa konstrukcja jest asymptotycznie szczelna; koniecznie . Wynika to np. Z wyniku Linial (1992) lub z prostego zastosowania teorii Ramseya. Ale dla mnie nie jest jasne, czy konstrukcja jest również szczelna do stałych. Niektóre eksperymenty numeryczne sugerują, że powyższa konstrukcja może być optymalna.$k = \Omega(\log c)$

Motywacja

Pytanie dotyczy istnienia szybko rozproszonych algorytmów kolorowania grafów. Załóżmy na przykład, że otrzymujemy ukierunkowane drzewo (wszystkie krawędzie są zorientowane w kierunku węzła głównego) i załóżmy, że otrzymujemy właściwe kolorowanie drzewa. Teraz istnieje rozproszony algorytm, który oblicza prawidłowe zabarwienie drzewa w synchronicznej rundzie komunikacyjnej wtedy i tylko wtedy, gdy .$c$$k$$1$$c \leadsto k$

Konstrukcja jest optymalna w tym sensie, że nie może utrzymać. Rzeczywiście, łatwo zauważyć, że c -to- K barwiących matrycy istnieje tylko wtedy, gdy istnieje c podzbiory ₁ , ..., _c z zestawu {1, ..., k }, że ma odrębne I i J zaspokoić _I ⊆ _j . (W kierunku „tylko jeśli” weź A _i = R ( M , i ) dla matrycy barwiącej c - to - k$\binom{2n}{n}+1 \leadsto n$M . Dla kierunku „if” ustaw m _ij ∈ A _i ∖ A _j .) Rodzina zbiorów, z których żaden nie zawiera innego, nazywa się rodziną Sperner , a twierdzenie Spernera, że ​​maksymalna liczba zbiorów w rodzinie Sperner na wszechświat wielkości k to . Oznacza to, że .$\binom{k}{\lfloor k/2\rfloor}$$c \leadsto k \iff c \le \binom{k}{\lfloor k/2\rfloor}$

W przypadku nieco mocniejszej asymptotyki można udowodnić, że:

jeśli , to$c \leadsto k$$c \leq 2^k$

Załóżmy, że występuje barwienie macierzy przy użyciu kolorów. Teraz pokoloruj każdy wiersz w macierzy według obecnego zestawu kolorów. To daje kolorowanie wierszy za pomocą podzbiorów . Różne rzędy muszą mieć różne kolory. W przeciwnym razie załóżmy, że dla rząd ma ten sam kolor co rząd . Oznacza to, że kolor jest obecny zarówno w wierszu iw kolumnie co jest sprzeczne z faktem, że zaczęliśmy od kolorowania. Wynika z tego, że$c \times c$$k$$[k]$$i \lt j$$i$$j$$(i,j)$$j$$j$$c \leq 2^k$