Dinitz theorem

Template:Short description Template:Distinguish 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,Template:R and proved in 1994 by Fred Galvin.Template:R

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.Template:R

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.Template:R

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.Template:R

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.Template:R

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.Template:R

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.Template:R

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.Template:R 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.Template:R Galvin settled the full conjecture in 1994 (published 1995) with the kernel argument above, which is elementary and self-contained.Template:R Expository accounts were given by ZeilbergerTemplate:R and in the textbook literature.Template:R

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.Template:R 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)\}$.Template:R

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.Template:R The Dinitz theorem is also related to Rota's basis conjecture.Template:R

External links

• Template:MathWorld