Dinitz Problem

Given any assignment of $n$-element sets to the $n^2$ locations of a square $n\times n$ array, is it always possible to find a Partial Latin Square? The fact that such a Partial Latin Square can always be found for a $2\times 2$ array can be proven analytically, and techniques were developed which also proved the existence for $4\times 4$ and $6\times 6$ arrays. However, the general problem eluded solution until it was answered in the affirmative by Galvin in 1993 using results of Janssen (1993ab) and F. Maffray.

See also Partial Latin Square

References

Chetwynd, A. and Häggkvist, R. ``A Note on List-Colorings.'' J. Graph Th. 13, 87-95, 1989.

Cipra, B. ``Quite Easily Done.'' In What's Happening in the Mathematical Sciences 2, pp. 41-46, 1994.

Erdös, P.; Rubin, A.; and Taylor, H. ``Choosability in Graphs.'' Congr. Numer. 26, 125-157, 1979.

Häggkvist, R. ``Towards a Solution of the Dinitz Problem?'' Disc. Math. 75, 247-251, 1989.

Janssen, J. C. M. ``The Dinitz Problem Solved for Rectangles.'' Bull. Amer. Math. Soc. 29, 243-249, 1993a.

Janssen, J. C. M. Even and Odd Latin Squares. Ph.D. thesis. Lehigh University, 1993b.

Kahn, J. ``Recent Results on Some Not-So-Recent Hypergraph Matching and Covering Problems.'' Proceedings of the Conference on Extremal Problems for Finite Sets. Visegràd, Hungary, 1991.

Kahn, J. ``Coloring Nearly-Disjoint Hypergraphs with $n+o(n)$ Colors.'' J. Combin. Th. Ser. A 59, 31-39, 1992.