Dinitz theorem

Short description: Theorem in combinatorics

Not to be confused with Dinitz-Garg-Goemans conjecture.

In combinatorics, the Dinitz theorem, formerly known as the Dinitz conjecture, is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin.

Statement

The Dinitz theorem states that, given an $n\times n$ square array, a set of $m$ symbols with $m\ge n$, and for each cell of the array an $n$-element set drawn from the pool of $m$ symbols, it is possible to label each cell with one of the elements of its set in such a way that no symbol is repeated within any row or any column. The resulting array is a partial Latin square: if all the cell sets happen to be the same set of $n$ symbols, the labeling is an ordinary $n\times n$ Latin square.

Formulation as list edge coloring

The theorem is most naturally expressed in the language of list coloring. For a graph $G$, a list assignment $L$ attaches to every edge $e$ a set $L(e)$ of permitted colors; a proper $L$-edge-coloring assigns to each edge a color from its own list so that adjacent edges (those sharing an endpoint) receive distinct colors. The list chromatic index $\chi {\text{'}}_{\ell }(G)$ is the least integer $k$ such that a proper $L$-edge-coloring exists for every list assignment with $|L(e)|\ge k$ for all edges $e$. Since one may always take identical lists, $\chi {\text{'}}_{\ell }(G)\ge {\chi }^{\prime }(G)\ge \mathrm{\Delta }(G)$, where ${\chi }^{\prime }$ is the ordinary chromatic index and $\mathrm{\Delta }$ the maximum degree.

An $n\times n$ Latin square corresponds to a proper edge coloring of the complete bipartite graph $K_{n,n}$ with $n$ colors: the two vertex classes are the rows and the columns, the edge joining row $i$ to column $j$ represents the cell $(i,j)$, and its color is the symbol placed in that cell. Under this correspondence, prescribing an $n$-element list for each cell is exactly prescribing an $n$-element list for each edge. The Dinitz theorem is therefore the statement that

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

Because $\mathrm{\Delta }(K_{n,n})=n$, this asserts that the list chromatic index of $K_{n,n}$ attains its smallest possible value.

Galvin's theorem

Galvin proved a considerably more general result: for every bipartite multigraph $G$,

$\chi {\text{'}}_{\ell }(G)={\chi }^{\prime }(G).$

By Kőnig's edge-coloring theorem the chromatic index of a bipartite multigraph equals its maximum degree, so $\chi {\text{'}}_{\ell }(G)=\mathrm{\Delta }(G)$. Taking $G=K_{n,n}$ recovers the Dinitz theorem.

Proof via kernels

Galvin's argument uses the notion of a kernel of a directed graph. A kernel of a digraph $D$ is a set $K$ of vertices that is independent (no arc joins two vertices of $K$) and absorbing (every vertex outside $K$ has an arc directed into $K$). The proof combines this with the following lemma, the kernel method.

Kernel lemma. Let $D$ be an orientation of a graph $G$ such that every induced subdigraph of $D$ has a kernel, and let $L$ be a list assignment (on the vertices) with $|L(v)|\ge d_D^{+}(v)+1$ for every vertex $v$, where $d_D^{+}(v)$ is the out-degree of $v$. Then $G$ has a proper $L$-coloring.

The lemma is proved by induction: choose a color $c$ appearing in some list, let $A$ be the set of vertices whose lists contain $c$, take a kernel $K$ of the subdigraph induced on $A$, color the vertices of $K$ with $c$, and delete $K$ from the graph together with $c$ from all remaining lists. Every vertex of $A\setminus K$ loses at least one out-neighbor, so the out-degree condition is preserved and induction applies.

To apply this to $L(K_{n,n})$, whose vertices are the $n^2$ cells $(i,j)$, fix a reference Latin square that assigns to cell $(i,j)$ a symbol $\sigma (i,j)\in \{1,\dots ,n\}$. Orient the line graph as follows: for two cells in the same row, direct the arc from the smaller reference symbol to the larger; for two cells in the same column, direct it from the larger to the smaller. Because the symbols in each row and each column form a permutation of $\{1,\dots ,n\}$, the cell $(i,j)$ with $\sigma (i,j)=s$ has exactly $n-s$ out-arcs within its row and $s-1$ within its column, giving out-degree

$d^{+}(i,j)=(n-s)+(s-1)=n-1$

for every cell. Lists of size $n=(n-1)+1$ thus satisfy the hypothesis of the kernel lemma.

Finally, every induced subdigraph has a kernel: a set of cells corresponds to a bipartite graph between rows and columns, and interpreting the reference symbols as preference rankings turns a kernel into a stable matching, which exists by the Gale–Shapley theorem. Hence $K_{n,n}$ is $n$-edge-choosable.

History

Dinitz posed the problem in 1979, and it circulated for over a decade as one of the best-known open questions on list coloring. Partial results preceded Galvin's solution: Jeannette Janssen proved the statement for $(n-1)\times n$ rectangular arrays, and for the square case with lists of size $n+1$, by applying the polynomial method of Alon and Tarsi. Galvin settled the full conjecture in 1994 (published 1995) with the kernel argument above, which is elementary and self-contained. Expository accounts were given by Zeilberger and in the textbook literature.

Generalizations

Galvin's proof extends verbatim from $K_{n,n}$ to all bipartite multigraphs, and more generally to line-perfect graphs by way of Maffray's characterization of the line graphs possessing kernels. Alexandr Kostochka, Borodin, and Woodall strengthened the bipartite result by allowing shorter lists: for a bipartite graph $G$, a proper edge coloring exists whenever each edge $uv$ is given a list of size at least $\max \{d_G(u),d_G(v)\}$.

The list edge-coloring conjecture (or list coloring conjecture) asserts that $\chi {\text{'}}_{\ell }(G)={\chi }^{\prime }(G)$ for every loopless multigraph, not just bipartite ones; it remains open in general. An even more general conjecture states that the list chromatic number of every claw-free graph equals its chromatic number. The Dinitz theorem is also related to Rota's basis conjecture.

External links

• Weisstein, Eric W.. "Dinitz Problem". http://mathworld.wolfram.com/DinitzProblem.html.