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 is odd the numbers of even and odd Latin squares are the same.
The Alon-Tarsi Conjecture: When is even the number of even Latin square is different from the number of odd Latin square.
This conjecture was proved when and
is prime by Drisko and when
and
is prime by Glynn. The first open case is
.
A stronger conjecture that is supported by known data is that when 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
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 . 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
) when
is even.
Let be a graph on
vertices
. Associate to every vertex
a variable
. Consider the graph polynomial
Alon and Tarsi considered the coefficient of the monomial
. If this coefficient is non-zero then they showed that for every lists of colors,
colors for vertex
, 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.
Pingback: To cheer you up in difficult times 9: Alexey Pokrovskiy proved that Rota’s Basis Conjecture holds asymptotically | Combinatorics and more