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

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

Latin squares Latin ( or ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken by the Latins in Latium (now known as Lazio), the lower Tiber area around Rome, Italy. Through the expansion o ...

, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin. 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 and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, that the list chromatic index of the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

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 In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mor ...

, the list chromatic index equals its

chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge colorin ...

. 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 (graph theory), claw as an induced subgraph. A claw is another name for the complete bipartite graph K_ (that is, a star graph comprising three edges, ...

s always equals their

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

. The Dinitz theorem is also related to

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

References

External links

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