Editar: ahora hay una pregunta de seguimiento relacionada con esta publicación.
Definiciones
Sean y enteros. Usamos la notación .
Se dice que una matriz es una matriz de color to- si se cumple lo siguiente:
- tenemos para todo ,
- para todo con y tenemos .
Escribimos si existe una matriz de colores c -to- k .
Tenga en cuenta que los elementos diagonales son irrelevantes; Estamos interesados sólo en los elementos no diagonales de .
La siguiente perspectiva alternativa puede ser útil. Sea sea el conjunto de elementos no diagonales en la fila , y de manera similar sea será el conjunto de elementos no diagonales en la columna . Ahora es una matriz de colores to- iff
Puede o no ser útil intentar interpretar como un tipo especial de función hash de a .
Ejemplos
Este es un -a-- matriz para colorear:
En general, se sabe que para cualquier tenemosPor ejemplo, y . Para ver esto, podemos usar la siguiente construcción (por ejemplo, Naor y Stockmeyer 1995).
Sea y sea . Sea una biyección de al conjunto de todos los subconjuntos de , es decir, y para todo . Para cada con , elija arbitrariamente
Tenga en cuenta que . Es sencillo verificar que la construcción sea de hecho una matriz de colores; en particular, tenemos y .
Pregunta
¿La construcción anterior es óptima? Dicho de otro modo, ¿tenemos para cualquier ?
Es bien sabido que la construcción anterior es asintóticamente apretada; necesariamente . Esto se sigue, por ejemplo, del resultado de Linial (1992) o de una aplicación directa de la teoría de Ramsey. Pero para mí no está claro si la construcción también está ajustada a las constantes. Algunos experimentos numéricos sugieren que la construcción anterior podría ser óptima.
Motivación
La pregunta está relacionada con la existencia de algoritmos distribuidos rápidamente para colorear gráficos. Por ejemplo, suponga que se nos da un árbol dirigido (todos los bordes orientados hacia un nodo raíz), y supongamos que se nos da un color adecuado del árbol. Ahora hay un algoritmo distribuido que calcula una coloración adecuada del árbol en ronda de comunicación síncrona si y solo si .
fuente
Respuestas:
La construcción es óptima en el sentido de que no puede sostenerse. De hecho, es fácil ver que la matriz de color c- to- k existe si y solo si hay c subconjuntos A 1 , ..., A c del conjunto {1, ..., k } de modo que ningún i y j distinto satisfagan A i ⊆ A j . (Para la dirección "solo si", tome A i = R ( M , i ) para una matriz de color c- to- k(2nn)+1⇝n M . Para la dirección "si", establezca m ij ∈ A i ∖ A j .) Una familia de conjuntos ninguno de los cuales contiene otro se llama familia Sperner , y es el teorema de Sperner que el número máximo de conjuntos en una familia Sperner en el el universo de tamaño k es . Esto implica que .(k⌊k/2⌋) c⇝k⟺c≤(k⌊k/2⌋)
fuente
Para un asintótico ligeramente más apretado, se podría demostrar que:
si , entoncesc⇝k c≤2k
Supongamos que hay una coloración de una matriz usando colores. Ahora, colorea cada fila de la matriz por el conjunto de colores presentes que contiene. Eso da una coloración de las filas usando subconjuntos de . Las diferentes filas deben tener diferentes colores. De lo contrario, suponga que para , la fila tiene el mismo color que la fila . Eso significa que el color de está presente tanto en la fila como en la columna que contradice el hecho de que comenzamos con una coloración. Se deduce quec×c k [k] i<j i j (i,j) j j c≤2k
fuente