Vorhandensein von "Farbmatrizen"

9

Bearbeiten: Es gibt jetzt eine Folgefrage zu diesem Beitrag.

Definitionen

Sei und ganze Zahlen. Wir verwenden die Notation . $c$ $k$ $[i] = \{1,2,...,i\}$

Eine Matrix wird als to- Farbmatrix bezeichnet, wenn Folgendes gilt: $c \times c$ $M = (m_{i,j})$ $c$ $k$

wir haben für alle , $m_{i,j} \in [k]$ $i, j \in [c]$
für alle mit und wir . $i,j,\ell \in [c]$ $i \ne j$ $j \ne \ell$ $m_{i,j} \ne m_{j,\ell}$

Wir schreiben wenn es eine to- Farbmatrix gibt. $c \leadsto k$ $c$ $k$

Beachten Sie, dass die diagonalen Elemente irrelevant sind. wir sind nur in den Nicht-Diagonalelemente von Interesse $M$ .

Die folgende alternative Perspektive kann hilfreich sein. Sei $R(M,\ell) = \{ m_{\ell,i} : i \ne \ell \}$ die Menge nichtdiagonaler Elemente in Zeile $\ell$ , und sei in ähnlicher Weise $C(M,\ell) = \{ m_{i,\ell} : i \ne \ell \}$ ist die Menge der nicht diagonalen Elemente in der Spalte $\ell$ . Nun ist $M$ eine $c$ to- $k$ Farbmatrix, wenn

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$ für alle

ℓ \in [c]

$\ell \in [c]$ . Das heißt, Zeile

ℓ

$\ell$ und Spalte

ℓ

$\ell$ müssen aus unterschiedlichen Elementen bestehen (außer natürlich in der Diagonale).

Es kann hilfreich sein oder auch nicht, zu versuchen, als eine spezielle Art von Hash-Funktion von bis zu interpretieren . $M$ $[c]^2$ $[k]$

Beispiele

Hier ist eine zu- Farbmatrix: $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}.$

Im Allgemeinen ist bekannt, dass wir für jedesZum Beispiel und . Um dies zu sehen, können wir die folgende Konstruktion verwenden (z. B. Naor & 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$

Sei und sei . Sei eine Bijektion von zur Menge aller Teilmengen von , dh und für alle . Wählen Sie für jedes mit beliebig $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).$

Beachten Sie, dass . Es ist einfach zu überprüfen, ob die Konstruktion tatsächlich eine Farbmatrix ist. insbesondere haben wir und . $f(j) \setminus f(i) \ne \emptyset$ $R(M,\ell) = f(\ell)$ $C(M,\ell) = [k] \setminus f(\ell)$

Frage

Ist die obige Konstruktion optimal? Anders , haben wir für jedes ?

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

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

n \geq 2

$n \ge 2$

Es ist bekannt, dass die obige Konstruktion asymptotisch dicht ist; notwendigerweise . Dies folgt beispielsweise aus dem Ergebnis von Linial (1992) oder aus einer einfachen Anwendung der Ramsey-Theorie. Mir ist aber nicht klar, ob die Konstruktion auch konstant ist. Einige numerische Experimente legen nahe, dass die obige Konstruktion optimal sein könnte. $k = \Omega(\log c)$

Motivation

Die Frage bezieht sich auf die Existenz schnell verteilter Algorithmen für die Farbgebung von Graphen. Nehmen wir zum Beispiel an, dass wir einen gerichteten Baum erhalten (alle Kanten sind auf einen Wurzelknoten ausgerichtet), und nehmen wir an, dass wir eine korrekte Färbung des Baums erhalten. Jetzt gibt es einen verteilten Algorithmus berechnet , dass ein ordnungsgemäßen des Baumes in Einfärben synchrone Kommunikationsrunde , wenn und nur wenn . $c$ $k$ $1$ $c \leadsto k$

co.combinatorics lower-bounds dc.distributed-comp Jukka Suomela
quelle

In der Anzeigemathematik in der „alternativen Perspektive“ sollte [c] [k] lauten. In der darauf folgenden Zeile sollte "für alle l \ in [k]" "für alle l \ in [c]" lauten.

Tsuyoshi Ito

9

Die Konstruktion ist in dem Sinne optimal, dass nicht halten kann. In der Tat ist leicht zu erkennen, dass die c- to- k- Farbmatrix genau dann existiert, wenn es c Teilmengen A ₁ ,…, A _c der Menge {1,…, k } gibt, so dass kein unterschiedliches i und j A erfüllen _i ⊆ A _j . (Für die "nur wenn" -Richtung nehmen Sie A _i = R ( M , i ) für eine c- to- k- Farbmatrix $\binom{2n}{n}+1 \leadsto n$ M . Für die "wenn" -Richtung setzen Sie m _ij ∈ A _i ∖ A _j .) Eine Familie von Mengen, von denen keine eine andere enthält, wird als Sperner-Familie bezeichnet , und es ist Sperners Theorem, dass die maximale Anzahl von Mengen in einer Sperner-Familie auf der Das Universum der Größe k ist . Dies impliziert, dass . $\binom{k}{\lfloor k/2\rfloor}$ $c \leadsto k \iff c \le \binom{k}{\lfloor k/2\rfloor}$

Tsuyoshi Ito
quelle

1

Oh, richtig, ich dachte, es sah so aus, als müssten die Reihen eine Sperner-Familie bilden, sah aber nicht, wie ich das beweisen sollte. Aber Sie haben absolut Recht: Wenn wir , dann , und daher . Das war einfach, vielen Dank!

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

Für eine etwas engere Asymptotik konnte nachgewiesen werden, dass:

wenn , dann $c \leadsto k$ $c \leq 2^k$

Angenommen, es gibt eine Färbung einer Matrix unter Verwendung von Farben. Färben Sie nun jede Zeile in der Matrix anhand der darin enthaltenen Farben. Dies ergibt eine Färbung der Zeilen unter Verwendung von Teilmengen von . Unterschiedliche Reihen müssen unterschiedliche Farben haben. Angenommen, für hat Zeile dieselbe Farbe wie Zeile . Das heißt, die Farbe von ist sowohl in Zeile als auch in Spalte was der Tatsache widerspricht, dass wir mit einer Färbung begonnen haben. Daraus folgt, dass $c \times c$ $k$ $[k]$ $i \lt j$ $i$ $j$ $(i,j)$ $j$ $j$ $c \leq 2^k$

hbm
quelle

Ich bin nicht sicher, was Sie behaupten, Ihre Analyse ist strenger als, aber bitte lesen Sie meine Antwort für die genaue Grenze.