Science Fair Project Encyclopedia
Dinitz conjecture
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.
10-26-2009 08:16:03
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
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