Combinatorial Nullstellensatz

Alon's Combinatorial Nullstellensatz is a powerful algebraic tool that transforms combinatorial problems into polynomial non-vanishing conditions. It has applications ranging from additive combinatorics to graph coloring and coding theory.

Statement

Theorem6.1Combinatorial Nullstellensatz (Alon 1999)

Let $\mathbb{F}$ be a field and let $f \in \mathbb{F}[x_1, \ldots, x_n]$ be a polynomial of degree $\deg(f) = \sum_{i=1}^n t_i$ , where $t_i$ are non-negative integers. Let $S_1, \ldots, S_n \subseteq \mathbb{F}$ with $|S_i| > t_i$ for each $i$ . If the coefficient of $\prod_{i=1}^n x_i^{t_i}$ in $f$ is nonzero, then there exists $(s_1, \ldots, s_n) \in S_1 \times \cdots \times S_n$ such that $f(s_1, \ldots, s_n) \neq 0$ .

Application to Additive Combinatorics

ExampleCauchy-Davenport Theorem

For prime $p$ and non-empty subsets $A, B \subseteq \mathbb{Z}_p$ : $|A + B| \geq \min(p, |A| + |B| - 1).$ Proof via Nullstellensatz: Set $|A| = a$ , $|B| = b$ , and suppose $|A + B| \leq a + b - 2$ . Let $C \supseteq A + B$ with $|C| = a + b - 2$ . Consider $f(x, y) = \prod_{c \in C}(x + y - c)$ , which has degree $a + b - 2$ and vanishes on $A \times B$ . The coefficient of $x^{a-1} y^{b-1}$ in $f$ is $\binom{a+b-2}{a-1} \neq 0 \pmod{p}$ , contradicting the Nullstellensatz.

RemarkKey Technique

The power of the Nullstellensatz lies in reducing the problem to computing a single coefficient. Often, the coefficient calculation involves binomial coefficients modulo a prime, where Kummer's theorem or Lucas's theorem can be applied.

Application to Graph Coloring

ExampleChoosability of Bipartite Graphs

Every bipartite graph $G$ satisfies $\operatorname{ch}(G) = \chi(G)$ , where $\operatorname{ch}$ denotes the list chromatic number. This was conjectured by Dinitz for the complete bipartite graph (the Dinitz conjecture) and proved by Galvin. The Nullstellensatz provides an alternative approach for specific cases by encoding proper colorings as non-roots of the graph polynomial $\prod_{\{i,j\} \in E} (x_i - x_j)$ .

Theorem6.2Alon-Tarsi Theorem

Let $G$ be a graph and $D$ an orientation of $G$ . If the number of Eulerian subgraphs with an even number of edges differs from the number with an odd number of edges, then the list chromatic number $\operatorname{ch}(G) \leq \Delta^+(D) + 1$ , where $\Delta^+(D)$ is the maximum out-degree.

RemarkPermanent and Latin Squares

The Alon-Tarsi theorem connects the permanent of certain matrices to the list chromatic number. It implies that every bipartite graph $K_{n,n}$ with $n$ even has $\operatorname{ch}(K_{n,n}) = n$ (the Dinitz conjecture). The proof uses the fact that the number of even and odd Latin squares of order $n$ differ when $n$ is even.