Combinatorial Nullstellensatz

One coefficient form of the Combinatorial Nullstellensatz says that if $\mathrm{deg}f\le d_1+\cdots +d_n$ and $[x_1^{d_1}\cdots x_n^{d_n}]f\ne 0$, then for every choice of sets $A_i$ with $|A_i|=d_i+1$ there is a point $(a_1,\dots ,a_n)\in A_1\times \cdots \times A_n$ at which $f$ does not vanish.

Suppose $|A|>|B|>0$ in ${\mathbb{F}}_p$. Put $a=|A|$ and $b^{\prime }=\min (|B|,p+2-a)$, and choose $B^{\prime }\subseteq B$ of size $b^{\prime }$. Let $r=a+b^{\prime }-2$. If the restricted sumset fits in a set $D$ of size $r-1$, then $(x-y){\prod }_{d\in D}(x+y-d)$ vanishes on $A\times B^{\prime }$. Its coefficient of $x^{a-1}{y}^{b^{\prime }-1}$ isAll factorial arguments are below $p$ and $0<a-b^{\prime }<p$. The Combinatorial Nullstellensatz gives a contradiction. Since $r=\min (p,|A|+|B|-2)$, this includes the saturated case as well as the small-set case.

For prime $p$, a graph with $m>(p-1)n$ edges and maximum degree at most $2p-1$ contains a nonempty $p$-regular subgraph. Over ${\mathbb{F}}_p$, apply the Combinatorial Nullstellensatz on the Boolean edge-variable cube toIts full squarefree coefficient is nonzero because the first product has degree below $m$. A nonzero value cannot occur at the zero vector; at any other Boolean vector the second product vanishes, and the first forces all selected degrees to be multiples of $p$. The maximum-degree condition makes every positive selected degree exactly $p$.

If an $n$ by $n$ matrix $A$ over a field has nonzero permanent, $b\in F^n$, and every $S_i\subseteq F$ has two elements, then some $x\in {\prod }_i{S}_i$ makes every coordinate of $Ax-b$ nonzero. Apply the Combinatorial Nullstellensatz towhose coefficient of $x_1\cdots x_n$ is $\mathrm{perm}A$.