Istnienie „matryc do barwienia”

9

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 - to - . $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, ℓ) \subseteq [k], C (M, ℓ) \subseteq [k], R (M, ℓ) \cap C (M, ℓ) = \emptyset

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

ℓ \in [c]

$\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{matrix} - & 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{matrix}] .

$\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$

(\binom{2 n}{n}) ⇝ 2 n .

${2n \choose n} \leadsto 2n.$

20 ⇝ 6

$20 \leadsto 6$

6 ⇝ 4

$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) ∖ f (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 ?

(\binom{2 n}{n}) + 1 ⇝ 2 n

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

n \geq 2

$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$

co.combinatorics lower-bounds dc.distributed-comp Jukka Suomela
źródło

W matematyce wyświetlacza w „alternatywnej perspektywie” [c] powinien brzmieć [k]. W następnym wierszu „dla wszystkich l \ in [k]” powinno brzmieć „dla wszystkich l \ in [c]”.

Tsuyoshi Ito

9

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}$

Tsuyoshi Ito
źródło

1

No tak, myślałem, że to wygląda na to, że rzędy będą musiały uformować rodzinę Spernerów, ale nie wiedziałem, jak to udowodnić. Ale masz całkowitą rację: jeśli mamy , to , a zatem . To było łatwe, wielkie dzięki!

R (M, i) \subseteq R (M, j)

$R(M,i) \subseteq R(M,j)$

m_{i, j} \in R (M, i) \subseteq R (M, j)

$m_{i,j} \in R(M,i) \subseteq R(M,j)$

C (M, j) \cap R (M, j) \neq \emptyset

$C(M,j) \cap R(M,j) \ne \emptyset$

Jukka Suomela

0

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$

Hbm
źródło

Nie jestem pewien, czy według ciebie analiza jest bardziej ścisła niż, ale proszę zobaczyć moją odpowiedź w celu uzyskania dokładnego ograniczenia.