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 A_{i,j} with n or more elements. Then it is possible to choose elements a_{ij} from A_{ij} such that the chosen elements in every row and in every colummn are distinct.

Special case: if all A_{ij} are the same set, say {1,2,…,n} then this is possible. Such a choice is called a Latin square for example a_{ij}=i+j({\rm mod} n).

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 A_i for vertex i we ask for a proper coloring of the graph such that vertex i is colored by an element of A_i. (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 A_i 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 K_{n,n}. 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 K_{n,n}. 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 v_1, ..., v_n such that vertex v_i has outdegree d_i assume that G has the following property

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

Then given any n sets A_1, \dots, A_n such that A_i has at least 1+d_i elements you can choose elements a_i from A_i such that if v_i and v_j are adjacent in G then a_i is different than a_j.

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

Proof: Choose some element -c- which is included in the union of all A_is. consider the subgraph G’ induced on the set W of all vertices v_i such that c belongs to A_i. 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 A_i. 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 (i_k,j_k) 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 n^2+n 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 a_{ij}. Now direct (i,j) toward (i,j’) if a_{ij}>a_{ij'} and direct (i,j) toward (i’,j) if a_{ij}<a_{i'j}. Sababa

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

About these ads
This entry was posted in Combinatorics, Games. Bookmark the permalink.

4 Responses to Galvin’s Proof of Dinitz’s Conjecture

  1. alef says:

    Typo: “.. Janssen applied a of Alon and Tarsi”,

    GK: Thanks, dear alef, corrected.

  2. alef says:

    shouldn’t “Ahla”! be “Achla”?

    • Gil Kalai says:

      Dear alef, I used consistently “ahla” but I saw “akhla” or “achla” also used. In hebrew it is אחלה. and I am not sure what the English way to write the ‘ח’ is.

      As a reminder: Arabic words which are part of Hebrew slang: ashkara – for real; sababa - cool, wonderful; walla – true; ahla – great; yalla - hurry up, c’mon, let’s go.

      We use walla, ahla, and sababa for the traditional \square.

  3. ja524309 says:

    Right after Lemma 1, you say
    “Let G be a directed graph with m vertices a_1 , … , a_n “. Am I missing something here, or shouldn’t you have used the same character for both m & n ?

    GK: Thanks!, corrected

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s