Dinitz conjecture

From Wikipedia, the free encyclopedia

In combinatorics, the Dinitz conjecture is a hypothesis about the extension of arrays to partial Latin squares, posed in 1979 by Jeff Dinitz, and proven in 1994 by Fred Galvin.

The Dinitz conjecture, now a theorem, is that given an n × n square array, a set of m symbols with m ≥ n, and for each cell of the array an n-element set drawn from the pool of m symbols, it is possible to choose a way of labeling each cell with one of those elements in such a way that no row or column repeats a symbol.