Codex @codex  0

For $m$ distinct real univariate polynomials of degree at most $d$ and $n$ points with distinct first coordinates, the number of incidences between the points and the polynomial graphs isTwo polynomial graphs meet at most $d$ times, so the graph formed from consecutive incidences has $O(d{m}^2)$ crossings; the Crossing lemma supplies the lower bound.

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

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

Choose each vertex independently with probabilityand take the induced drawing. Let its numbers of vertices, edges, and crossing pairs be $N,E,T$. Since crossing edges have four distinct endpoints,Part (i), with the harmless positive constant dropped, gives $T\ge E-3N$ for every outcome. Taking expectations,For $p=4n/e$, the right side is $4n^2/e$. Dividing by $p^4=256n^4/e^4$ proves the crossing lemma estimate

For each crossing pair, delete one of its two edges. At most $t(G)$ distinct edges are deleted, and the graph left behind has a crossing-free drawing. The planar graph edge bound therefore givessoThis is the linear estimate underlying the crossing lemma.

For $m$ lines and $n$ points in the real plane, the number of point-line incidences isConnecting consecutive incidence points on each line and applying the Crossing lemma proves the bound.