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)

Another way to Revolutionize Football

The angle of Victoria Beckham’s hat (here in a picture from a recent wedding) is closely related to our previous post on football

One of the highlights of the recent Newton Institute  conference on discrete harmonic analysis was a football game which was organized by Frank Barthe and initiated independently by Barthe and Prasad Tetali. There were two teams of 10 players (more or less), I was the oldest player on the field, and it was quite exciting. No spontaneous improvement of my football skills has occurred since my youth.

All the lectures at the conference were videotaped and can be found here. (The football game itself was not videotaped.) Let me mention an idea for a new version of football which occurred to me while playing. For an early suggested football revolution and some subsequent theoretical discussions see this post on football and the intermediate value theorem.

The New Football Game

There are four teams. Team L (the left team), Team R (the right team), Team D (the defense team) and team O (the offense team.)  The left team protects the left goal and tries to score the right goal, the right team protects the right goal and tries to score the left goal, the defense team tries to prevent goals on both sides of the field and the offense team tries to score as much as possible goals on both sides of the field.

In formal terms,  define X to be the number of goals scored to the right and Y the number of goals scored to the left. Then the four teams try to maximize X-Y, Y-X, -X-Y and X+Y, respectively. (I do not assume teams A and B change position at halftime, but the formula can easily be adjusted.)

Is Backgammon in P?

The Complexity of Zero-Sum Stochastic Games with Perfect Information

Is there a polynomial time algorithm for chess?  Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is “no”. But if we wish to consider the complexity in terms of the number of all possible positions then it is easy to go backward over all positions and determine what is the outcome of the game when we start with each given position.

Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form $2^{n^{\alpha}}$ for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding if this is possible was an open problem for several decades. Here is a link to the paper.

Update: Oliver Friedmann have managed to use similar methods to find similar lower bounds also for Zadeh’s deterministic pivot rule. See this paper.

We can regard the simplex algorithm as starting from an arbitrary vertex of the feasible polytope and repeatedly moving to a neighboring vertex with a higher value of the objective function according to some pivot rule.

The pivot rules considered in the paper are

RANDOM EDGE– Choose an improving pivoting step uniformly at random.

RANDOM FACET– Choose at random a facet containing your vertex and apply the algorithm in that facet.

Test Your Intuition (13): How to Play a Biased “Matching Pennies” Game

Recall the game “matching pennies“. Player I has to chose between ‘0’ or ‘1’, player II has to chose between ‘0’ and ‘1’.No player knows what is the choice of the other player before making his choice. Player II pays to player I one dollar if the two number match and gets one dollar from player I  if they do not match.

The optimal way to play the game for each of the player is via a mixed strategy. Player I has to choose ‘0’ with probability 1/2 and ‘1’ with probability 1/2. And so is player II.

Now, suppose that the game is the same except that if the outcomes match and both player chose ‘1’ player II pays 5 dollars to player I and not one dollar. (All other payoffs remain at one dollar.)

Test your intuition: What is the probability player I should play ‘1’. (More than 1/2? less than 1/2? more than 1/3? less than 1/3? more than 2/3? less than 2/3?)

Futures Trading as a Game of Luck

A recent interesting article by Ariel Rubinstein entitled “Digital Sodom” (in Hebrew) argues that certain forms of  futures trading (and Internet sites where these forms of trading take place) are essentially gambling activities.

The issue of “what is gambling” is very intereting. In an earlier post entitled “Chess can be a game of luck” the interesting question regarding “games of luck” and “games of skill” was discussed. It was argued that for a betting game, if, over time, for all players (or even for most players), the expected gains are negative, then we can regard the game as primarily a game of luck. (The claim is that this is a reasonable interpretation of the current law, even if not the only possible interpretation.)

Chess can be a Game of Luck

Can chess be a game of luck?

Let us consider the following two scenarios:

A) We have a chess tournament where each of forty chess players pay 50 dollars entrance fee and the winner takes the prize which is 80% of the the total entrance fees.

B)  We have a chess tournament where each of forty chess players pay 20,000 dollars entrance fee and the winner takes the prize which is 80% of the the total entrance fees.

Before dealing with these two rather realistic scenarios let us consider the following more hypothetical situations.

C) Suppose that chess players have a quality measure that allows us to determine the probability that any one player will beat the other. Two players play and bet. The strong player bets 10 dollars  and the waek player bets according to the probability he will win. (So the expected gain of both player is zero.)

D)  Suppose again that chess players have a quality measure that allows us to determine the probability that any one players will beat the other. Two players play and bet. The strong player bets 100,000 dollars and the weak player bets according to the probability he will wins. (Again, the expected gain of both players is zero.)

When we analyze scenarios C and D the first question to ask is “What is the game?” In my opinion we need to consider the entire setting, so the “game” consists of both the chess itself and the betting around it. In cases C and D the betting aspects of the game are completely separated from the chess itself. We can suppose that the higher the stakes are, the higher the ingredient of luck of the combined game. It is reasonable to assume that version C) is mainly a game of skill and version D) is mainly a game of luck.

Now what about the following scenarios:

E) Two players play chess and bet 5 dollars.

Here the main ingredient is skill; the bet only adds a little spice to the game.

F) Two players play chess and bet 100,000 dollars.

Well, to the extent that such a game takes place at all, I would expect that the luck factor will be dominant. (Note that scenario F is not equivalent to the scenario where two players play, the winner gets 300,000 dollars and the loser gets 100,000 dollars.)

Let us go back to the original scenarios A) and B). Here too, I would consider the ingredients of luck and skill to be strongly dependant on the stakes. The setting of scenario A) can be quite compatible with a game of skill where the prizes give some extra incentives to participants (and rewards for the organizers), while in scenario B) it stands to reason that the luck/gambling factor will be dominant.

One critique against my opinion is: What about tennis tournaments where professional tennis players are playing on large amounts of prize money? Are professional tennis tournaments  games of luck? There is one major difference between this example and examples A and B above. In tennis tournaments there are very large prizes but the expected gain for a player is positive, all (or at least most) players can make a living by participating. This changes entirely the incentives. This is also the case for various high level professional chess tournaments.

For mathematicians there are a few things that sound strange in this analysis. The luck ingredient is not invariant under multiplying the stakes by a constant, and it is not invariant under giving (or taking) a fixed sum of money to the participants before the game starts. However, these aspects are crucial when we try to analyze the incentives and motives of players and, in my opinion,  it is a mistake to ignore them.

So my answer is: yes, chess can be a game of luck.

Social Choice Talk

I took part in a workshop celebrating the publication of a new book on Social Choice by Shmuel Nitzan which took place at the Open University. (The book is in Hebrew, and an English version is forthcoming from Cambridge University Press.) It was a very interesting event and all the lectures were excellent. I thought of blogging about my lecture.

The main part of the lecture was about the four old theorems in the table above and about what should replace the two question marks. The left side of the table deals with properties of the majority voting rule for binary preferences. The right side of the table is about general voting rules. On the top tight is the famous Arrow Impossibility Theorem. The table is filled by two theorems I proved in 2002 (in this paper) and it now looks like this: Continue reading

Do Politicians Act Rationally?

Well, I wrote an article (in Hebrew) about it in the Newspaper Haaretz. An English translation appeared in the English edition. Here is an appetizer:

During World War II, many fighter planes returned from bombing missions in Japan full of bullet holes. The decision was made to reinforce the planes, and their natural tendency was to bolster the hardest-hit sections in the body of the plane. However, the mathematician George Dantzig suggested that it was precisely the parts that were hit less that needed to be armored. Was he right?

Months after all the commentators described Hillary Clinton’s chances as so slim she was bound to lose her campaign for the Democratic presidential nomination, she continued to fight for her candidacy, saying she believed she would win and keeping up her attack on her rival. Did she act rationally? And did Benjamin Netanyahu and Tzipi Livni act rationally when each declared victory on election night? Did Meretz supporters who voted for Kadima act rationally? Is there an election method in which it would be rational for all voters to vote in accordance with their genuine preferences?

My conclusion is:

Which Coalition to Form (2)?

Yair Tauman

(This post is a continuation of this previous post.)

Aumann and Myerson proposed that if political and ideological matters are put aside, the party forming the coalition would (or should) prefer to form the coalition in which its own power (according to the Shapley-Shubik power index) is maximal. They expected that this idea would have some predictive value  —  even in reality, where political and ideological considerations are of importance. A few days ago Yair Tauman, another well-known Israeli game theorist, mentioned on TV this recipe as a normative game-theoretic recommendation in the context of the recent Israeli elections. (For Yair’s analysis see also this article. (I even sent a critical comment.))

Over the years, Aumann was quite fond of this suggestion and often claimed that in Israeli elections it gives good predictions in some (but not all) cases. The original paper mentions the Israeli 1977 elections and how delighted one of the authors was that four months after the elections a major “centrist” party joined the coalition, leading to a much better Shapley value for the party forming the coalition.

I was quite skeptical about the claim that the maximum-power-to-the-winning-party rule has any predictive value and in 1999 with the help of Sergiu Hart I decided to test this claim. I asked Aumann which Israeli coalition he regards as fitting his prediction the best. His answer was the 1988 election where Shamir’s party, the Likud, had a very large Shapley value in the coalition it formed. We checked how high the Shapley value was compared to a random coalition that the winning party could have formed. Continue reading