Galvin’s Proof of Dinitz’s Conjecture

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)

Let G be a directed graph with n vertices such that vertex has outdegree assume that G has the following property

(*) Every induced subgraph of G has a kernel.

Then given any n sets such that has at least elements you can choose elements from such that if and are adjacent in then is different than .

In other words you can color the graph such that the color of is chosen from and no two adgacent vertices are colored by the same color. (Let us call the set of colors for vertex .)

Proof: Choose some element –c- which is included in the union of all s. consider the subgraph G’ induced on the set W of all vertices such that c belongs to . G’ has a kernel K. Now color the vertices in K by the color -c- (this is ok, since -c- is in their set of colors and they form an independent set.) delete the vertices of K from the graph and delete the color -c– from all the remaining sets . The condition applies to the reaining graph – the color sets for vertices not in W remain the same and for vertices in W\K the color set is reduced by one color but so is the outdegree since every reaining vertex in W had an edge directed to K. The lemma follows by induction. Walla!

Consider the graph G whose vertices are the pairs (i,j) and two vertices are adgacent if one of their coordinates agree. Consider an orientation of the edges of our graph such that the orientation induced on any row and any column is acyclic.

Lemma 2: The resulting directed graph has the property (*).

This result was proved by Frédéric Maffray  [JCT Ser B 1992]. It is, in fact, an extension of the famous Gale-Shapley stable marriage theorem and the original proof by Gale and Shapley works as well.

Consider the rows as a set of n men and the columns as a set of n women consider the direction on the cells of the i-th row as the preferences of the i-th men, if (i,j) is directed toward (i,j’) then the i-th man prefer woman j’ over woman j. The same rule goes with the women. An induced subgraph correspond to a partial list of pairs (i,j) we can consider this list as the list of pairs of (man, woman) that knows each other.

Property (*) for the entire graph is just the Gale-Shapley stable marriage theorem. For induced subgraphs it is a slight generalization for which the original (algorithmic) proof of the Gale-Shapley theorem works.

GALE-SHAPLEY THEOREM (slightly extended) Consider a society of n men and n women and collection C of pairs (i,j) representing men and women that knows each other. Assume that every man [and every woman] have a preference (linear) relation on the women [men] he [she] knows. Then there is a stable marriage, namely a set M of pairs such that every man and woman appears in at most one pair and for every pair (i,j) in C\ M there is either a pair (i,j’) in M such that man i prefers woman j’ on woman j, or there is a pair (i’,j) in M such that woman j prefers man i’ on man i.

Proof: Consider the following algorithm, on day 1 every man goes to the first woman on his list and every woman select the best man among those who come to her and reject the others. on the second day every rejected men go to the second woman on his list and every woman select one man from all man that comes to her (including the man she selected in the first day if there was such a man) and rejects all others, and so on. This process will terminate after finitely many days and with a stable marriage! To see that the process terminate note that each day at least one man will come to a new women, or go back home after beeing rejected from every women (n+1 possibilities) and none of these possibilitie will ever repeat itself so after at most days things will stabilize. When it terminates we have a stable marriage because suppose women W and men M are not married at the end. If M is married to a women he prefers less then W or to no women at all it means that M visited W and she rejected him so she had a better men than M.  Ahla!

To prove Dinits conjecture all that is left is:

Fact 3: there is an an orientation of our graph of pairs such that every row and every colun are directed acyclic and all outdegrees are n-1.

Proof: consider a latin square with entries 1,2,…,n (like the one described above) so each cell (i,j) is occupied with Now direct (i,j) toward (i,j’) if and direct (i,j) toward (i’,j) if . Sababa! 

REMARK: There is also a simple inductive proof of (*) for this particular orientation.

Advertisements