Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 161 (Topics in Combinatorics)

Let $X$ be the number of crossings in the drawing, placed in general position. Deleting at most one edge at each crossing leaves a planar graph, so the Euler formula for a connected planar graph gives

Now retain every vertex independently with probability $p$, together with every edge whose endpoints survive. The expected numbers of retained vertices, edges and crossings are $pn,p^{2}m,p^{4}X$. Applying the preceding inequality to each sampled drawing and taking expectations givesBecause $m\ge 6n$, choose $p=6n/m\le 1$. Thenand thereforeThus the Crossing lemma holds here with the absolute constant $c=1/72$.

Regard each equation $P_i(x_j)=y_j$ as an incidence between the point $(x_j,y_j)$ and the graph of $P_i$. On each polynomial graph, join consecutive incident points by the intervening arc. If $I$ is the number of incidences, the resulting topological graph hasedges and $n$ vertices.

Two distinct degree-$d$ polynomial graphs meet in at most $d$ points because a nonzero polynomial of degree at most $d$ has at most $d$ real roots. Their drawn arcs therefore create at most $d$ genuine crossings. Parallel arcs with the same endpoints may be perturbed to cross once; for each pair of polynomials, such crossing-free lenses occur only between consecutive roots of their difference and hence at most $d$ times. The total number of genuine and added crossings is consequentlyAfter these perturbations, a crossing-free subgraph is simple, so the sampling proof of the Crossing lemma applies to this topological graph.

If $M<6n$, then $I<m+6n$. Otherwise the crossing lemma givesand henceSince $I\le M+m$, both cases combine to prove the incidences between points and polynomial graphs boundfor an absolute constant $C$.

The chain rule for information entropy and conditioning reduces entropy giveThus subadditivity of information entropy holds for two finitely valued random variables. Applying this inequality to $(X_1,\dots ,X_{n-1})$ and $X_n$ and then inducting gives

Shearer's inequality states that if $X=(X_1,\dots ,X_n)$ is a discrete random vector and $\mathcal{F}$ is a collection of subsets of $[n]$ in which every index occurs at least $t$ times, then

Order the coordinates naturally. For every $F\in \mathcal{F}$, the chain rule for information entropy givesRemoving conditioning variables cannot decrease entropy, so every summand is at leastAfter summing over $F$, each index $i$ contributes at least $t$ times. A final application of the chain rule yieldswhich proves the lemma.

Choose $A$ uniformly from $\mathcal{A}$, and let $X_i=1_{\{i\in A\}}$. The characteristic vector of a set determines $A$, soFor $F\in \mathcal{F}$, the projected vector $X_F$ determines the intersection $A\cap F$ and therefore takes values in the trace of a set family $T_F(\mathcal{A})$. The maximum-entropy bound on a finite set givesEvery coordinate belongs to at least $t$ members of $\mathcal{F}$, so Shearer's inequality givesExponentiation proves the Shearer trace inequality

The coefficient form of the Combinatorial Nullstellensatz is the following. Let $f\in F[x_1,\dots ,x_n]$ have total degree at most $d_1+\cdots +d_n$, and supposeFor arbitrary subsets $S_i\subseteq F$ with $|S_i|=d_i+1$, there is an $x\in S_1\times \cdots \times S_n$ such that $f(x)\ne 0$.

For the proof, defineSuccessive Lagrange interpolation in the variables gives the Alon-Tarsi lemmaEvery denominator is nonzero because the elements of $S_i$ are distinct. If $f$ vanished throughout the product grid, the right side and hence the assumed nonzero coefficient would vanish. This contradiction proves the theorem.

Consider the degree-$n$ polynomialTo form the square-free monomial $x_1\cdots x_n$, one must choose each variable exactly once from the $n$ factors. Such choices are indexed by permutations, soThis coefficient is nonzero by hypothesis. Apply the Combinatorial Nullstellensatz with every $d_i=1$ and the given two-element sets $S_i$. It supplies $x\in {\prod }_i{S}_i$ with $f(x)\ne 0$. Every factor is then nonzero, sofor all $i$. This is coordinate avoidance from a nonzero permanent.

For each $A\in \mathcal{A}$, define over ${\mathbb{F}}_p$Replace every power $x_i^r$ with $r\ge 1$ by $x_i$; this does not change the values on characteristic vectors of sets and produces a multilinear polynomial of degree at most $m$.

At the characteristic vector of $B\in \mathcal{A}$,This is zero when $A\ne B$, whereasThe evaluation matrix is diagonal with nonzero diagonal, so the polynomials $P_A$ are linearly independent. The space of multilinear polynomials of degree at most $m$ has the monomial basis ${\prod }_{i\in S}{x}_i$ for $|S|\le m$ and dimension ${\sum }_{i=0}^m\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. Hence the modular intersection bound for a set family gives

Let $\mathcal{A}$ be an independent set in the graph. Every member has size $p^2\equiv 0(\mathrm{mod}p)$, while for distinct $A,B\in \mathcal{A}$, independence means $|A\cap B|$ is nonzero modulo $p$. Apply part i withThis givesMoreover,

Let $\mathcal{C}$ be a clique and choose the given prime $q$ with $p^2<q<2p^2$. For distinct $A,B\in \mathcal{C}$, the intersection size is a multiple of $p$ strictly below $p^2$. In ${\mathbb{F}}_q$, setThese are $p$ distinct residues because $q>p^2$, every off-diagonal intersection size lies in $E$, and the diagonal size $p^2$ does not. Part i, now over ${\mathbb{F}}_q$, yieldsThe subsets of a $p^3$-element set having size at most $p$ inject into its ordered $p$-tuples: list a nonempty subset increasingly and repeat its final element, while assigning the empty set one decreasing tuple not used in this way. The injection is not surjective, so

Put $k=p^{3p}$. Parts ii and iii give a graph with neither a clique nor an independent set of size $k$. Its number of vertices satisfies the standard binomial lower boundConsequently the modular-intersection graph Ramsey lower bound gives

For every fixed $C>0$,The first quantity exceeds the second when $p>3C$. Thus $p^{p^2}$ is eventually larger than $k^C$ for every fixed $C$, so this lower bound grows faster than every polynomial in $k$.