Teorema de Dinitz

En combinatoria , el teorema de Dinitz , anteriormente conocido como la conjetura de Dinitz , es un enunciado sobre la extensión de arreglos a cuadrados latinos parciales , propuesto en 1979 por Jeff Dinitz , ^{[ 1 ]} y demostrado en 1994 por Fred Galvin . ^{[ 2 ] [ 3 ]}

El teorema de Dinitz establece que, dado un${\displaystyle n\times n}$matriz cuadrada, un conjunto de${\displaystyle m}$símbolos con${\displaystyle m\geq n}$y para cada celda de la matriz un${\displaystyle n}$-conjunto de elementos extraído del grupo de${\displaystyle m}$símbolos, es posible etiquetar cada celda con uno de los elementos de su conjunto de tal manera que ningún símbolo se repita dentro de ninguna fila o ninguna columna. La matriz resultante es un cuadrado latino parcial : si todos los conjuntos de celdas resultan ser el mismo conjunto de${\displaystyle n}$símbolos, el etiquetado es ordinario${\displaystyle n\times n}$Plaza latina. ^{[ 4 ]}

El teorema se expresa de forma más natural en el lenguaje de la coloración de listas . Para un grafo${\displaystyle G}$, una asignación de lista${\displaystyle L}$se adhiere a cada borde${\displaystyle e}$un conjunto${\displaystyle L(e)}$de colores permitidos; un adecuado${\displaystyle L}$-edge-coloring asigna a cada borde un color de su propia lista, de modo que los bordes adyacentes (aquellos que comparten un punto final) reciben colores distintos. El índice cromático de la lista${\displaystyle \chi '_{\ell }(G)}$es el entero más pequeño${\displaystyle k}$de tal manera que un adecuado${\displaystyle L}$-edge-coloring existe para cada asignación de lista con${\displaystyle |L(e)|\geq k}$para todos los bordes${\displaystyle e}$. Dado que siempre se pueden tomar listas idénticas,${\displaystyle \chi '_{\ell }(G)\geq \chi '(G)\geq \Delta (G)}$, dónde${\displaystyle \chi '}$es el índice cromático ordinario y${\displaystyle \Delta }$el grado máximo.

Un${\displaystyle n\times n}$El cuadrado latino corresponde a una coloración de aristas adecuada del grafo bipartito completo.${\displaystyle K_{n,n}}$con${\displaystyle n}$colores: las dos clases de vértices son las filas y las columnas, la arista que une la fila${\displaystyle i}$a la columna${\displaystyle j}$representa la célula${\displaystyle (i,j)}$y su color es el símbolo colocado en esa celda. Bajo esta correspondencia, prescribir un${\displaystyle n}$-la lista de elementos para cada celda prescribe exactamente una${\displaystyle n}$-lista de elementos para cada arista. Por lo tanto, el teorema de Dinitz es la afirmación de que

${\displaystyle \chi '_{\ell }(K_{n,n})=n.}$

Porque${\displaystyle \Delta (K_{n,n})=n}$, esto afirma que la lista índice cromático de${\displaystyle K_{n,n}}$alcanza su valor mínimo posible. ^{[ 4 ] [ 3 ]}

Galvin demostró un resultado considerablemente más general: para cada multigrafo bipartito${\displaystyle G}$,

${\displaystyle \chi '_{\ell }(G)=\chi '(G).}$

Según el teorema de coloración de aristas de Kőnig, el índice cromático de un multigrafo bipartito es igual a su grado máximo, por lo que${\displaystyle \chi '_{\ell }(G)=\Delta (G)}$. Tomando${\displaystyle G=K_{n,n}}$recupera el teorema de Dinitz. ^{[ 2 ] [ 5 ]}

Dinitz planteó el problema en 1979, y circuló durante más de una década como una de las preguntas abiertas más conocidas sobre coloración de listas. ^{[ 1 ] [ 4 ]} Resultados parciales precedieron a la solución de Galvin: Jeannette Janssen demostró la afirmación para${\displaystyle (n-1)\times n}$matrices rectangulares, y para el caso cuadrado con listas de tamaño${\displaystyle n+1}$, aplicando el método polinomial de Alon y Tarsi. ^{[ 8 ]} Galvin resolvió la conjetura completa en 1994 (publicada en 1995) con el argumento del núcleo anterior, que es elemental y autocontenido. ^{[ 2 ] Zeilberger [ 3 ]} y en la literatura de libros de texto dieron explicaciones . ^{[ 6 ] [ 9 ]}

La prueba de Galvin se extiende textualmente desde${\displaystyle K_{n,n}}$a todos los multigrafos bipartitos, y más generalmente a los grafos perfectos de líneas a través de la caracterización de Maffray de los grafos de líneas que poseen núcleos. ^{[ 10 ]} Alexandr Kostochka , Borodin y Woodall reforzaron el resultado bipartito al permitir listas más cortas: para un grafo bipartito${\displaystyle G}$, existe un color de borde adecuado siempre que cada borde${\displaystyle uv}$se le da una lista de tamaño al menos${\displaystyle \max\{d_{G}(u),d_{G}(v)\}}$. ^{[ 5 ]}

La conjetura de coloración de aristas de listas (o conjetura de coloración de listas) afirma que${\displaystyle \chi '_{\ell }(G)=\chi '(G)}$Para todo multigrafo sin bucles, no solo los bipartitos; permanece abierto en general. Una conjetura aún más general afirma que el número cromático de lista de todo grafo sin garras es igual a su número cromático . ^{[ 11 ]} El teorema de Dinitz también está relacionado con la conjetura de la base de Rota . ^{[ 4 ]}

• Weisstein, Eric W. "Problema Dinitz" . MundoMatemático .