combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...

, the Dinitz theorem (formerly known as Dinitz conjecture) is a statement about the extension of arrays to partial

Latin squares In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin s ...

, proposed in 1979 by

Jeff Dinitz Jeffrey Howard Dinitz (born 1952) is an American mathematician who taught combinatorics at the University of Vermont. He is best known for proposing the Dinitz conjecture, which became a major theorem. Dinitz is married to Susan Dinitz and has t ...

, and proved in 1994 by

Fred Galvin Frederick William Galvin is a mathematician, currently a professor at the University of Kansas. His research interests include set theory and combinatorics. His notable combinatorial work includes the proof of the Dinitz conjecture. In set theory, ...

. The Dinitz 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. It can also be formulated as a result in

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, that the list chromatic index of the complete bipartite graph

K_

equals

n

. That is, if each edge of the complete bipartite graph is assigned a set of

n

colors, it is possible to choose one of the assigned colors for each edge such that no two edges incident to the same vertex have the same color. Galvin's proof generalizes to the statement that, for every bipartite multigraph, the list chromatic index equals its chromatic index. The more general edge list coloring conjecture states that the same holds not only for bipartite graphs, but also for any loopless multigraph. An even more general conjecture states that the list chromatic number of

claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph ''K''1,3 (that is, a star graph comprising three edges, three leaves, ...

s always equals their chromatic number. The Dinitz theorem is also related to

Rota's basis conjecture In linear algebra and matroid theory, Rota's basis conjecture is an unproven conjecture concerning rearrangements of bases, named after Gian-Carlo Rota. It states that, if ''X'' is either a vector space of dimension ''n'' or more generally a matr ...

References

External links

* Combinatorics Latin squares Graph coloring Theorems in discrete mathematics Conjectures Conjectures that have been proved {{combin-stub