## Dinitz’ conjecture

The following theorem was conjectured by Jeff Dinitz in 1979 and proved by Fred Galvin in 1994:

**Theorem:** Consider an *n* by *n* square table such that in each cell *(i,j)* you have a set with *n* or more elements. Then it is possible to choose elements from such that the chosen elements in every row and in every colummn are distinct.

*Special case:* if all are the same set, say *{1,2,…,n} *then this is possible. Such a choice is called a **Latin square **for example .

1 2 3 4

2 3 4 1

3 4 1 2

4 1 2 3

Here are a few remarks before we go ahead with Galvin’s proof:

1) The Theorem is about graph-coloring from lists of colors, or briefly **list-coloring**. Given a graph *G* with *n* vertices and a list of colors for vertex we ask for a proper coloring of the graph such that vertex* i* is colored by an element of . (A proper coloring is a coloring such that two djacent vertices have different colors.)

The **list chromatic number** of a graph *G* is the smallest number *k* such that *G* can be colored from any lists of colors, where every has *k* elements.

2) We consider the graph G whose vertices are the pairs* (i,j)* and two vertices are adgacent if one of their coordinates agree. This graph is the** line graph** of the complete bipartite graph . The line graph* L(H)* of a graph *H* is the graph whose vertices correspond to the edges of *H* and two vertices are adjacent if the corresponding edges share a vertex.

3) Vizing proved that the chromatic number of the line graph *L(H)* is at most one more than the maximum degree of *H*. He conjectured that this is also true for list coloring. A bolder version asserts that for every line-graph* G* the list chromatic number equals the chromatic number. Dinits’s conjecture is the special case (of the bolder version) where *G* is the line graph of the complete bipartite graph . The proof demonstrates Vizing’s conjecture for the line graph of every bipartite graph.

4) Shortly before Galvin, Jeannette Janssen gave an amazing proof for a slightly weaker statement where in each square you allow* n+1* colors. (She proved the Dinitz conjecture for rectangular arrays.) Janssen applied a theorem of Alon and Tarsi, who used the “polynomial method” to obtain a powerful necessary condition for list coloring.

5) Here are now (or when I will be able to find them later) links to Galvin’s paper, to Janssen’s paper, to Alon-Tarsi’s paper, to expositions by Barry Cipra and by Doron Zeilberger and to a short self-contained version of the proof by Tomaž Slivnik.

## Galvin’s proof

Galvin’s ingenious proof of Dinitz’ the conjecture combines two known theorems which are quite easy themselves.

For a directed graph *G* an **induced subgraph** is a subgraph spanned by a subset of the set of vertices of* G*. A **kernel** in a directed graph is an independent and absorbant set of vertices. I.e., it is a set of vertices *W* such that there is no edge between any two vertices in* W*, and from every vertex not in W there is an edge directed from it to a vertex in* W*.

**Lemma 1** (Bondy, Boppana, Siegal): (mentioned e.g. in the paper by Alon and Tarsi)

Continue reading →