Dinitz conjecture

From Wikipedia, the free 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 proven 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.