Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 11 / 3

The coefficient form of the Combinatorial Nullstellensatz is as follows. Let $F$ be a field, let $P\in F[x_1,\dots ,x_r]$ have total degree at most $t_1+\cdots +t_r$, and suppose the coefficient of $x_1^{t_1}\cdots x_r^{t_r}$ is nonzero. For finite subsets $S_i\subset F$ with $|S_i|>t_i$, there is a point of $S_1\times \cdots \times S_r$ where $P$ is nonzero.

For completeness, restrict to $|S_i|=t_i+1$. The coefficient identity isBy Lagrange interpolation, the one-variable weighted sum on the right kills powers below $t_i$ and equals one on the power $t_i$. Any monomial of total degree at most $\sum t_i$, other than the specified one, has some exponent below $t_i$ and therefore contributes zero; the specified monomial contributes its coefficient. Every denominator is nonzero in the field. Hence a nonzero coefficient forces a nonzero grid value. The two applications below use this coefficient form.

Choose a fixed prime $p\ge k$, and put $s=2p-2$. We first derive the polynomial step: a graph $H$ on $N$ vertices and $M>(p-1)N$ edges, with maximum degree at most $2p-1$, contains a nonempty $p$-regular subgraph. Use a Boolean variable $x_e$ for each edge and work over ${\mathbb{F}}_p$. DefineThe first product has degree at most $(p-1)N<M$, while the full squarefree monomial ${\prod }_e{x}_e$ has coefficient $(-1{)}^{M+1}\ne 0$ in the second term with its minus sign. The Combinatorial Nullstellensatz, with every grid $\{0,1\}$, gives a nonzero value of $R$. Since $R(0)=0$, this is a nonempty edge selection. The second product is then zero, so the first is nonzero. Fermat's little theorem makes each selected vertex degree zero modulo $p$. The maximum-degree bound implies that every positive selected degree is precisely $p$. This proves the prime-regular subgraph from Boolean polynomial constraints.

We next turn density into an almost-regular bipartite subgraph, keeping the logarithmic loss explicit. Let the original graph have $n\ge 2$ vertices and $m>0$ edges. Some bipartition retains at least $m/2$ edges: choose the sides independently with probability $1/2$ and average the number crossing. Its average degree is at least $m/n$. Repeatedly delete a vertex of degree at most half the current average degree. Such a deletion cannot lower that average, sinceThe process cannot delete the last positive-density graph, because the maintained average is positive. At termination the minimum degree is an integer $\sigma >m/(2n)$.

Choose the larger side $A$ of this remaining bipartite graph, with opposite side $B$. Keep exactly $\sigma$ edges at each vertex of $A$; choices at different vertices of $A$ do not conflict. Remove any now-isolated vertices of $B$. Thus $|A|\ge |B|$, and every vertex of $A$ has degree $\sigma$.

Such a half-regular graph contains a half-regular restriction with a perfect matching. Choose a minimal nonempty $X\subseteq A$ satisfying $|N(X)|\le |X|$, which exists because the whole side $A$ satisfies this inequality. In fact equality holds: if it were strict, deleting a vertex of $X$ would retain the inequality, contradicting minimality; the singleton case has at least one neighbor. Every proper subset $Y\subset X$ satisfies $|N(Y)|\ge |Y|$. Hall's marriage theorem therefore supplies a perfect matching on $X\cup N(X)$. All $\sigma$ edges incident with each vertex of $X$ remain inside that restriction.

Delete this perfect matching and repeat the restriction argument. The left degrees decrease by one at each step. We obtain $\sigma$ edge-disjoint perfect matchings $M_0,\dots ,M_{\sigma -1}$ on nested nonempty vertex sets, with sizesFor any $i$ with $i+s\le \sigma -1$, the union of $s+1=2p-1$ consecutive matchings in a graph has maximum degree at most $2p-1$ and at least $(s+1)N_{i+s}/2$ edges on $N_i$ vertices. Ifit has more than $(p-1)N_i$ edges, so the polynomial step yields a $p$-regular bipartite subgraph. Every regular bipartite graph decomposes into perfect matchings: for a set in one part, counting incident edges gives Hall's inequality, so a perfect matching exists; remove it and repeat. Choosing $k$ of these $p$ matchings in a graph gives a nonempty $k$-regular subgraph. This is the nested matching criterion for a regular subgraph.

If no $k$-regular subgraph exists, every displayed size ratio must therefore satisfy the reverse inequality. Iterating at indices $0,s,2s,\dots$ gives, with $r=\lfloor (\sigma -1)/s\rfloor$,Consequently $r\le \log n/\log ((s+1)/s)$ andCombining with $\sigma >m/(2n)$ proves the required edge bound. For example the finite constantworks for every $n\ge 2$, and the case $n=1$ has no edges. ThusThe logarithm comes from how often a nested matching in a graph vertex set can shrink by a fixed factor before becoming empty; it is not supplied by the polynomial step alone.

Write $a=|A|$ and $b=|B|$, so $p\ge a>b\ge 1$. To cover both the unsaturated and saturated cases with the same coefficient calculation, setChoose $B^{\prime }\subseteq B$ of size $b^{\prime }$. These parameters satisfy $1\le b^{\prime }<a\le p$ and $1\le r\le p$.

Assume, for a contradiction, that the restricted sumset $C$ has fewer than $r$ elements. Extend it to a subset $D\subseteq {\mathbb{F}}_p$ of size $r-1$, and formOn $A\times B^{\prime }$, this polynomial vanishes: when $x=y$ the first factor vanishes, and when $x\ne y$ the sum belongs to $C\subseteq D$. Its total degree is $r=(a-1)+(b^{\prime }-1)$. Only the leading homogeneous part $(x-y)(x+y{)}^{r-1}$ contributes to the coefficient of $x^{a-1}{y}^{b^{\prime }-1}$. That coefficient isThe equality includes $b^{\prime }=1$, with an out-of-range binomial coefficient interpreted as zero. All factorial arguments are between zero and $p-1$, and $0<a-b^{\prime }<p$, so this coefficient is nonzero in ${\mathbb{F}}_p$. The Combinatorial Nullstellensatz applied to $A\times B^{\prime }$ forces a nonzero value, contradicting the vanishing just proved. Hence the restricted sumset bound for unequal subsets of a prime field isThe strict size inequality is used precisely in the nonzero factor $a-b^{\prime }$. The argument includes $r=p$ without dividing by $p!$, so no separate saturation assumption is hidden.