Alon-Tarsi Number

The Alon-Tarsi number of a graph is the least positive integer such that the graph polynomial of contains a monomial with nonzero coefficient in which every variable has exponent less than . To write the definition explicitly, label the vertices of by , ..., , choose a graph orientation of its edges, and form

(1)

If

(2)

then equivalently

(3)

It is independent of the chosen graph orientation and is an upper bound for the choice number of by the combinatorial nullstellensatz (Alon and Tarsi 1992).

More generally, the same formula defines the Alon-Tarsi number of a nonzero polynomial. For a hypergraph with and no empty hyperedges, a hypergraph polynomial has the form

(4)

where every coefficient is nonzero. The polynomial is fully balanced when its coefficients are equal within each hyperedge. Multiplying each factor by a nonzero scalar then normalizes those coefficients to 1. It is fully unbalanced when every hyperedge has at least two unequal coefficients. Anholcer et al. (2026) prove that the fully balanced polynomial over a field of field characteristic zero has Alon-Tarsi number , where

(5)

is the edge density, and denotes the ceiling function. For a fully unbalanced hypergraph polynomial, its coefficients can be permuted within the hyperedges so that the resulting Alon-Tarsi number is at most .