Existência de "matrizes de coloração"

9

Editar: agora existe uma pergunta de acompanhamento relacionada a esta postagem.


Definições

Seja c e k números inteiros. Usamos a notação [i]={1,2,...,i} .

Um c×c matriz M=(mi,j) é dito ser um c Para- k coloração matriz se mantém o seguinte:

  • temos mi,j[k] para todos i,j[c] ,
  • para todos os i,j,[c] com ij e j temos mi,jmj, .

Escrevemos ck se existe uma matriz de coloração c to- k .


Observe que os elementos diagonais são irrelevantes; Estamos interessados apenas nos elementos não diagonais de M .

A seguinte perspectiva alternativa pode ser útil. Deixe- R(M,)={m,i:i} ser o conjunto de elementos não diagonais em linha , e semelhante deixar C(M,)={mi,:i} seja o conjunto de elementos não diagonais na coluna . Agora M é um c Para- k coloração matriz sse

R(M,)[k],C(M,)[k],R(M,)C(M,)=
para todos[c] . Ou seja, a linha e a coluna devem consistir em elementos distintos (exceto, é claro, na diagonal).

Pode ou não ser útil tentar interpretar como um tipo especial de função hash de [ c ] 2 a [ k ] .M[c]2[k]

Exemplos

Aqui está uma matriz de coloração a- 4 : [ - 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 - ] .64

[221113311144111322324224234343].

Em geral, sabe-se que para qualquer temos ( 2 nn2Por exemplo,206e64. Para ver isso, podemos usar a seguinte construção (por exemplo, Naor & Stockmeyer 1995).

(2nn)2n.
20664

Seja e sejak=2n. Sejafuma bijeção de[c]para o conjunto de todos osn-conjuntos de[2n], ou seja,f(i)[2n]e| f(i)| =npara todosi. Para cadai,j[c]comijc=(2nn)k=2nf[c]n[2n]f(i)[2n]|f(i)|=nii,j[c]ij, escolha arbitrariamente

mi,jf(i)f(j).

Observe que . É fácil verificar se a construção é realmente uma matriz de coloração; em particular, temos R ( M , ) = f ( ) e C ( M , ) = [ k ] f ( ) .f(j)f(i)R(M,)=f()C(M,)=[k]f()

Questão

A construção acima é ideal? Em outras palavras, temos para qualquern2?

(2nn)+12n
n2

É sabido que a construção acima é assintoticamente estanque; necessariamente . Isto se segue, por exemplo, do resultado de Linial (1992) ou de uma aplicação direta da teoria de Ramsey. Mas, para mim, não está claro se a construção também é rígida para constantes. Algumas experiências numéricas sugerem que a construção acima pode ser ótima.k=Ω(logc)

Motivação

A questão está relacionada à existência de algoritmos distribuídos rapidamente para colorir gráficos. Por exemplo, suponha que recebamos uma árvore direcionada (todas as arestas orientadas para um nó raiz) e suponha que recebamos uma cor adequada da árvore. Agora, existe um algoritmo distribuído que calcula uma coloração k adequada da árvore em 1 rodada de comunicação síncrona se e somente se c k .ck1ck

Jukka Suomela
fonte
Na tela de matemática, na “perspectiva alternativa”, [c] deve ler [k]. Na linha seguinte, “para todos os l \ in [k]” deve ler “para todos os l \ in [c]”.
Tsuyoshi Ito

Respostas:

9

A construção é ótima no sentido de que (2nn)+1 1n M(kk/2)ckc(kk/2)

Tsuyoshi Ito
fonte
11
R(M,i)R(M,j)mi,jR(M,i)R(M,j)C(M,j)R(M,j)
0

Para um assintótico um pouco mais apertado, pode-se provar que:

ckc2k

c×ck[k]i<jij(i,j)jjc2k

hbm
fonte
Não sei ao certo o que você está afirmando que sua análise é mais rigoroso, mas veja minha resposta para o limite exato.
Tsuyoshi Ito