Hypergraph extension of the Alon-Tarsi list coloring theorem (Q2387187): Difference between revisions

In a list coloring of a (hyper)graph the assignments of colors to the vertices have to be chosen from a list of colors associated to each vertex. A (hyper)graph is \(d\)-choosable if a coloring of the vertices avoiding monochromatic edges can be chosen from the lists whenever all lists have size at least \(d\). Alon-Tarsi's theorem says that a graph is \(d\)-choosable if it possesses an orientation such that the outdegree of every vertex is less than \(d\) and with the property that the number of circulations with an odd number of edges differs from the number of circulations with an even number edges. The aim of the paper is to generalize this result to \(k\)-uniform hypergraphs for prime \(k\). The proof makes use of the algebraic methods applied by Alon and Tarsi; for this purpose hypergraph polynomials are introduced.