Existence de «matrices colorantes»

Modifier: il y a maintenant une question de suivi liée à ce message.

---

Définitions

Soit et entiers. Nous utilisons la notation .k [ i ] = { 1 , 2 , . . . , i $c$$k$$[i] = \{1,2,...,i\}$

Une matrice est dite matrice de coloration to- si les conditions suivantes sont réunies :M = ( m i , j ) c k$c \times c$$M = (m_{i,j})$$c$$k$

• nous avons pour tout ,i , j ∈ [ c $m_{i,j} \in [k]$$i, j \in [c]$
• pour tout avec et nous avons .i ≠ j j ≠ ℓ m i , j ≠ m j , $i,j,\ell \in [c]$$i \ne j$$j \ne \ell$$m_{i,j} \ne m_{j,\ell}$

c $c \leadsto k$$c$$k$

---

Notez que les éléments diagonaux ne sont pas pertinents; nous ne nous intéressons aux éléments non diagonaux de .$M$

La perspective alternative suivante peut être utile. Soit l'ensemble des éléments non diagonaux de la ligne , et de même, soit l'ensemble des éléments non diagonaux dans la colonne . Maintenant, est une matrice de coloration to- si pour tous les \ ell \ dans [c] . C'est-à-dire que la ligne \ ell et la colonne \ ell doivent être constituées d'éléments distincts (sauf, bien sûr, en diagonale).ℓ C ( M , ℓ ) = { m i , ℓ : i ≠ ℓ } ℓ M c k R ( M , ℓ ) ⊆ [ k ] $R(M,\ell) = \{ m_{\ell,i} : i \ne \ell \}$$\ell$$C(M,\ell) = \{ m_{i,\ell} : i \ne \ell \}$$\ell$$M$$c$$k$ℓ ∈ [ c ] ℓ

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

Il peut être utile ou non d'essayer d'interpréter comme un type spécial de fonction de hachage de à .[ c ] 2 [ k $M$$[c]^2$$[k]$

Exemples

Voici un -vers-- matrice coloration:4 [ - 2 2 1 1 1 3 - 3 1 1 1 4 4 - 1 $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}.$$

En général, on sait que pour tout nous avonsPar exemple, et . Pour voir cela, nous pouvons utiliser la construction suivante (par exemple, Naor & Stockmeyer 1995).( 2 $n \ge 2$20⇝66⇝

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

Soit et soit . Soit une bijection de vers l'ensemble de tous les ensembles de , c'est-à-dire et pour tout . Pour chaque avec , choisissez arbitrairement k=2nf[c]n[2n]f(i)⊆[2n]| f(i)| =$c = {2n \choose n}$$k = 2n$$f$$[c]$$n$$[2n]$$f(i) \subseteq [2n]$$|f(i)| = n$i , j ∈ [ c ] i ≠ j m i , j ∈ f ( i ) ∖ f ( j ) $i$$i,j \in [c]$$i \ne j$

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

Notez que . Il est simple de vérifier que la construction est bien une matrice colorante; en particulier, nous avons et .$f(j) \setminus f(i) \ne \emptyset$$R(M,\ell) = f(\ell)$$C(M,\ell) = [k] \setminus f(\ell)$

Question

La construction ci-dessus est-elle optimale? Autrement dit, avons-nous pour ?

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

Il est bien connu que la construction ci-dessus est asymptotiquement étanche; nécessairement . Cela découle, par exemple, du résultat de Linial (1992) ou d'une application directe de la théorie de Ramsey. Mais pour moi, il n'est pas clair si la construction est également étanche aux constantes. Certaines expériences numériques suggèrent que la construction ci-dessus pourrait être optimale.$k = \Omega(\log c)$

Motivation

La question est liée à l'existence d'algorithmes distribués rapidement pour la coloration des graphes. Par exemple, supposons que l'on nous donne un arbre dirigé (tous les bords orientés vers un nœud racine), et supposons que l'on nous donne un coloring approprié de l'arbre. Il existe maintenant un algorithme distribué qui calcule une coloration correcte de l'arbre en tour de communication synchrone si et seulement si .k 1 c ⇝ $c$$k$$1$$c \leadsto k$

La construction est optimale dans le sens où ne peut pas tenir. En effet, il est facile de voir que la matrice de coloration c- to- k existe si et seulement s'il y a c sous-ensembles A ₁ ,…, A _c de l'ensemble {1,…, k } de sorte qu'aucun i et j distincts ne satisfassent A _i ⊆ A _j . (Pour la direction «seulement si», prendre A _i = R ( M , i ) pour une matrice de coloration c- to- k$\binom{2n}{n}+1 \leadsto n$M . Pour la direction «si», définissez m _ij ∈ A _i ∖ A _j .) Une famille d'ensembles dont aucun n'en contient une autre est appelée famille Sperner , et c'est le théorème de Sperner que le nombre maximum d'ensembles dans une famille l'univers de taille k est . Cela implique que .$\binom{k}{\lfloor k/2\rfloor}$$c \leadsto k \iff c \le \binom{k}{\lfloor k/2\rfloor}$

Pour une asymptotique légèrement plus serrée, il pourrait être prouvé que:

si , alors$c \leadsto k$$c \leq 2^k$

Supposons qu'il existe une coloration d'une matrice utilisant couleurs. Maintenant, coloriez chaque ligne de la matrice par le jeu de couleurs qu'elle contient. Cela donne une coloration des lignes en utilisant des sous-ensembles de . Différentes lignes doivent avoir des couleurs différentes. Sinon, supposons que pour , la ligne ait la même couleur que la ligne . Cela signifie que la couleur de est présente à la fois à la ligne et à la colonne ce qui contredit le fait que nous avons commencé par une coloration. Il s'ensuit quek [ k ] i < j i j ( i , j ) j j c ≤ 2 $c \times c$$k$$[k]$$i \lt j$$i$$j$$(i,j)$$j$$j$$c \leq 2^k$