Test Your Intuition (27) 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.

	Aleksander Coho on Elchanan Mossel’s Amazin…
	Gil Kalai on Gil’s Collegial Quantum…
	TYI 41: How many ste… on Gil’s Collegial Quantum…
	The story of Poincar… on Gil’s Collegial Quantum…
	Gil Kalai on Gil’s Collegial Quantum…
	Peter Shor on Gil’s Collegial Quantum…
	Gil Kalai on Gil’s Collegial Quantum…
	Peter Shor on Gil’s Collegial Quantum…
	Gil Kalai on Lior, Aryeh, and Michael
	Gil Kalai on Gil’s Collegial Quantum…
	Google, IBM, and the… on Quantum computers: amazing pro…
	Not Quite Getting Up… on Gil’s Collegial Quantum…