Science Fair Project Encyclopedia
In combinatorics, the Dinitz conjecture was a problem on the extension of arrays to partial Latin squares, posed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin.
Given an n × n square array, and a set of m symbols with m ≥ n, we suppose given for each cell of the array an n-element set of the symbols. The Dinitz conjecture, now a theorem, is that it is then possible to choose a way of labelling each cell with one of those elements, in such a way that no row or column repeats a symbol.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details