Editar: agora existe uma pergunta de acompanhamento relacionada a esta postagem.
Definições
Seja e números inteiros. Usamos a notação .
Um matriz é dito ser um Para- coloração matriz se mantém o seguinte:
- temos para todos ,
- para todos os com e temos .
Escrevemos se existe uma matriz de coloração to- .
Observe que os elementos diagonais são irrelevantes; Estamos interessados apenas nos elementos não diagonais de .
A seguinte perspectiva alternativa pode ser útil. Deixe- ser o conjunto de elementos não diagonais em linha , e semelhante deixar seja o conjunto de elementos não diagonais na coluna . Agora é um Para- coloração matriz sse
Pode ou não ser útil tentar interpretar como um tipo especial de função hash de [ c ] 2 a [ 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 - ] .
Em geral, sabe-se que para qualquer temos ( 2 nPor exemplo,20⇝6e6⇝4. Para ver isso, podemos usar a seguinte construção (por exemplo, Naor & Stockmeyer 1995).
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]comi≠j, escolha arbitrariamente
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 ( ℓ ) .
Questão
A construção acima é ideal? Em outras palavras, temos para qualquern≥2?
É 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.
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 .
fonte
Respostas:
A construção é ótima no sentido de que( 2nn) +1⇝n M(k⌊k/2⌋) c⇝k⟺c≤(k⌊k/2⌋)
fonte
Para um assintótico um pouco mais apertado, pode-se provar que:
fonte