A study relating the Alon-Tarsi number of a hypergraph polynomial p_H (the product, over all edges, of a linear expression in the incident vertex variables) to the edge density red(H) of the hypergraph. The paper proves AT(p_H) = red(H) + 1 when all coefficients equal 1, and its main result shows that for arbitrary nonzero coefficients they can be permuted within each edge so the resulting polynomial p'_H satisfies AT(p'_H) <= 2 red(H) + 1. It conjectures the permutation is unnecessary, which would yield a significant generalization of the 1-2-3 Conjecture.
Given a hypergraph H = (V, E), one assigns to each edge a linear expression in the vertex variables and forms the hypergraph polynomial p_H as the product of these linear expressions over all edges. …