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

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