Dinitz theorem

☆ Save On Wikipedia ↗

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,[1] and proved in 1994 by Fred Galvin.[2][3]

Statement

The Dinitz theorem states that, given an n × n {\displaystyle n\times n} {\displaystyle n\times n} square array, a set of m {\displaystyle m} {\displaystyle m} symbols with m ≥ n {\displaystyle m\geq n} {\displaystyle m\geq n}, and for each cell of the array an n {\displaystyle n} {\displaystyle n}-element set drawn from the pool of m {\displaystyle m} {\displaystyle 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 {\displaystyle n} {\displaystyle n} symbols, the labeling is an ordinary n × n {\displaystyle n\times n} {\displaystyle n\times n} Latin square.[4]

Formulation as list edge coloring

The theorem is most naturally expressed in the language of list coloring. For a graph G {\displaystyle G} {\displaystyle G}, a list assignment L {\displaystyle L} {\displaystyle L} attaches to every edge e {\displaystyle e} {\displaystyle e} a set L ( e ) {\displaystyle L(e)} {\displaystyle L(e)} of permitted colors; a proper L {\displaystyle L} {\displaystyle 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 χ ℓ ′ ( G ) {\displaystyle \chi '_{\ell }(G)} {\displaystyle \chi '_{\ell }(G)} is the least integer k {\displaystyle k} {\displaystyle k} such that a proper L {\displaystyle L} {\displaystyle L}-edge-coloring exists for every list assignment with | L ( e ) | ≥ k {\displaystyle |L(e)|\geq k} {\displaystyle |L(e)|\geq k} for all edges e {\displaystyle e} {\displaystyle e}. Since one may always take identical lists, χ ℓ ′ ( G ) ≥ χ ′ ( G ) ≥ Δ ( G ) {\displaystyle \chi '_{\ell }(G)\geq \chi '(G)\geq \Delta (G)} {\displaystyle \chi '_{\ell }(G)\geq \chi '(G)\geq \Delta (G)}, where χ ′ {\displaystyle \chi '} {\displaystyle \chi '} is the ordinary chromatic index and Δ {\displaystyle \Delta } {\displaystyle \Delta } the maximum degree.

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

χ ℓ ′ ( K n , n ) = n . {\displaystyle \chi '_{\ell }(K_{n,n})=n.} {\displaystyle \chi '_{\ell }(K_{n,n})=n.}

Because Δ ( K n , n ) = n {\displaystyle \Delta (K_{n,n})=n} {\displaystyle \Delta (K_{n,n})=n}, this asserts that the list chromatic index of K n , n {\displaystyle K_{n,n}} {\displaystyle K_{n,n}} attains its smallest possible value.[4][3]

Galvin's theorem

Galvin proved a considerably more general result: for every bipartite multigraph G {\displaystyle G} {\displaystyle G},

χ ℓ ′ ( G ) = χ ′ ( G ) . {\displaystyle \chi '_{\ell }(G)=\chi '(G).} {\displaystyle \chi '_{\ell }(G)=\chi '(G).}

By Kőnig's edge-coloring theorem the chromatic index of a bipartite multigraph equals its maximum degree, so χ ℓ ′ ( G ) = Δ ( G ) {\displaystyle \chi '_{\ell }(G)=\Delta (G)} {\displaystyle \chi '_{\ell }(G)=\Delta (G)}. Taking G = K n , n {\displaystyle G=K_{n,n}} {\displaystyle G=K_{n,n}} recovers the Dinitz theorem.[2][5]

Proof via kernels

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

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

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

To apply this to L ( K n , n ) {\displaystyle L(K_{n,n})} {\displaystyle L(K_{n,n})}, whose vertices are the n 2 {\displaystyle n^{2}} {\displaystyle n^{2}} cells ( i , j ) {\displaystyle (i,j)} {\displaystyle (i,j)}, fix a reference Latin square that assigns to cell ( i , j ) {\displaystyle (i,j)} {\displaystyle (i,j)} a symbol σ ( i , j ) ∈ { 1 , … , n } {\displaystyle \sigma (i,j)\in \{1,\dots ,n\}} {\displaystyle \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 , … , n } {\displaystyle \{1,\dots ,n\}} {\displaystyle \{1,\dots ,n\}}, the cell ( i , j ) {\displaystyle (i,j)} {\displaystyle (i,j)} with σ ( i , j ) = s {\displaystyle \sigma (i,j)=s} {\displaystyle \sigma (i,j)=s} has exactly n − s {\displaystyle n-s} {\displaystyle n-s} out-arcs within its row and s − 1 {\displaystyle s-1} {\displaystyle s-1} within its column, giving out-degree

d + ( i , j ) = ( n − s ) + ( s − 1 ) = n − 1 {\displaystyle d^{+}(i,j)=(n-s)+(s-1)=n-1} {\displaystyle d^{+}(i,j)=(n-s)+(s-1)=n-1}

for every cell. Lists of size n = ( n − 1 ) + 1 {\displaystyle n=(n-1)+1} {\displaystyle 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 {\displaystyle K_{n,n}} {\displaystyle K_{n,n}} is n {\displaystyle n} {\displaystyle n}-edge-choosable.[2][7][6]

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.[1][4] Partial results preceded Galvin's solution: Jeannette Janssen proved the statement for ( n − 1 ) × n {\displaystyle (n-1)\times n} {\displaystyle (n-1)\times n} rectangular arrays, and for the square case with lists of size n + 1 {\displaystyle n+1} {\displaystyle n+1}, by applying the polynomial method of Alon and Tarsi.[8] Galvin settled the full conjecture in 1994 (published 1995) with the kernel argument above, which is elementary and self-contained.[2] Expository accounts were given by Zeilberger[3] and in the textbook literature.[6][9]

Generalizations

Galvin's proof extends verbatim from K n , n {\displaystyle K_{n,n}} {\displaystyle 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.[10] Alexandr Kostochka, Borodin, and Woodall strengthened the bipartite result by allowing shorter lists: for a bipartite graph G {\displaystyle G} {\displaystyle G}, a proper edge coloring exists whenever each edge u v {\displaystyle uv} {\displaystyle uv} is given a list of size at least max { d G ( u ) , d G ( v ) } {\displaystyle \max\{d_{G}(u),d_{G}(v)\}} {\displaystyle \max\{d_{G}(u),d_{G}(v)\}}.[5]

The list edge-coloring conjecture (or list coloring conjecture) asserts that χ ℓ ′ ( G ) = χ ′ ( G ) {\displaystyle \chi '_{\ell }(G)=\chi '(G)} {\displaystyle \chi '_{\ell }(G)=\chi '(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.[11] The Dinitz theorem is also related to Rota's basis conjecture.[4]

References

  1. Erdős, P.; Rubin, A. L.; Taylor, H. (1979). "Choosability in graphs". Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata (PDF). Congressus Numerantium. Vol. 26. pp. 125–157. Archived from the original (PDF) on 2016-03-09. Retrieved 2017-04-22.
  2. F. Galvin (1995). "The list chromatic index of a bipartite multigraph". Journal of Combinatorial Theory. Series B. 63 (1): 153–158. doi:10.1006/jctb.1995.1011.
  3. Zeilberger, D. (1996). "The method of undetermined generalization and specialization illustrated with Fred Galvin's amazing proof of the Dinitz conjecture". American Mathematical Monthly. 103 (3): 233–239. arXiv:math/9506215. doi:10.2307/2975373. JSTOR 2975373.
  4. Chow, T. Y. (1995). "On the Dinitz conjecture and related conjectures" (PDF). Discrete Mathematics. 145 (1–3): 73–82. doi:10.1016/0012-365X(94)00055-N.
  5. Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. (1997). "List edge and list total colourings of multigraphs". Journal of Combinatorial Theory. Series B. 71 (2): 184–204. doi:10.1006/jctb.1997.1780.
  6. Aigner, Martin; Ziegler, Günter M. (2018). "The Dinitz problem". Proofs from THE BOOK (6th ed.). Springer. doi:10.1007/978-3-662-57265-8.
  7. Gale, D.; Shapley, L. S. (1962). "College admissions and the stability of marriage". American Mathematical Monthly. 69 (1): 9–15. doi:10.1080/00029890.1962.11989827. JSTOR 2312726.
  8. Janssen, Jeannette C. M. (1993). "The Dinitz problem solved for rectangles". Bulletin of the American Mathematical Society. New Series. 29 (2): 243–249. arXiv:math/9310232. doi:10.1090/S0273-0979-1993-00430-1.
  9. Diestel, Reinhard (2017). Graph Theory. Graduate Texts in Mathematics. Vol. 173 (5th ed.). Springer. §5.4, List Colouring. doi:10.1007/978-3-662-53622-3.
  10. Maffray, Frédéric (1992). "Kernels in perfect line-graphs". Journal of Combinatorial Theory. Series B. 55 (1): 1–8. doi:10.1016/0095-8956(92)90028-V.
  11. Gravier, Sylvain; Maffray, Frédéric (2004). "On the choice number of claw-free perfect graphs". Discrete Mathematics. 276 (1–3): 211–218. doi:10.1016/S0012-365X(03)00292-9. MR 2046636.