Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 161 / 1

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$.