Test Your Intuition about the Alon-Tarsi Conjecture

On the occasion of Polymath 12 devoted to the Rota basis conjecture let me remind you about the Alon-Tarsi conjecture and test your intuition concerning a strong form of the conjecture.

The sign of a Latin square is the product of signs of rows (considered as permutations) and the signs of columns. A Latin square is even if its sign is 1, and odd if its sign is -1. It is easy to see that when n is odd the numbers of even and odd Latin squares are the same.

The Alon-Tarsi Conjecture: When n is even the number of even Latin square is different from the number of odd Latin square.

This conjecture was proved when n=p+1 and p is prime by Drisko and when n=p-1 and p is prime by Glynn. The first open case is n=26.

A stronger conjecture that is supported by known data is that when n is even there are actually more even Latin squares than odd Latin squares. (This table is taken from the Wolfarm mathworld page on the conjecture.)

Test your intuition: Are there more even Latin squares than odd Latin squares when n is even?

A poll

Unlike previous “test your intuition” questions the answer is not known.

 

The Alon Tarsi-Theorem

The Alon-Tarsi conjecture arose in the context of coloring graphs from lists. Alon and Tarsi proved a general theorem regarding coloring graphs when every vertex has a list of colors and the conjecture comes from applying the general theorem to Dinits’ conjecture that can be regarded as a statement about list coloring of the complete bipartite graph K_{n,n}. In 1994 Galvin proved the Dinitz conjecture by direct combinatorial proof. See this post. Gian-Carlo Rota and Rosa Huang proved that the Alon-Tarsi conjecture implies the Rota basis conjecture (over \mathbb R) when n is even.

Let G be a graph on n vertices \{1,2,\dots, n\}. Associate to every vertex i a variable x_i. Consider the graph polynomial P_G(x_1,\dots ,x_n)=\prod \{(x_i-x_j) i<j, \{i,j\} \in E(G)\}. Alon and Tarsi considered the coefficient of the monomial \prod_{i=1}^d x_i^{d_i}. If this coefficient is non-zero then they showed that for every lists of colors, d_i+1 colors for vertex i, there is a legal coloring of the vertices from the lists! Alon and Tarsi went on to describe  combinatorially the coefficient as the difference between numbers of even and odd Euler orientations.

Let me mention the paper by Jeannette Janssen  The Dinitz problem solved for rectangles that contains a proof based on Alon-Tarsi theorem of a rectangle case of Dinitz conjecture. It is very interesting if the polynomial used by Janssen can be used to prove a “rectangular” (thus a bit weaker) version of the Rota’s basis conjecture. A similar slightly weaker form of the conclusion of Rota’s basis  conjecture is conjectured by Ron Aharoni and Eli Berger in much much greater generality.

Advertisements
This entry was posted in Combinatorics, Open problems, Test your intuition and tagged , . Bookmark the permalink.

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