Counting the number of lines

Question

Show that there exists a constant $A$ such that for any $n$ points in $\mathbf R^2$, when $2\le k\le \sqrt n$, there are at most $\frac{An^2}{k^3}$ lines passing through at least $k$ points.

Observing the result $An^2\over k^3$, it seems that crossing lemma is useful in the proof. But I have no idea how to transform this question into a graph problem.

Thanks in advance for your help.

Answer 1

Take all $m$ lines passing through at least $k$ of the points. Construct the graph $G$ whose vertex set is the $n$ points, with an edge between two points whenever they're consecutive points along a line. (That is, a line passing through $\ell$ points will be split up into $\ell-1$ edges.)

We stick with the natural embedding of this graph in the plane: leave the points where they are, and draw the edges as straight line segments.

We know the following:

• Whenever two edges cross, the lines they come from cross, which happens once per pair of lines: at most $\binom m2$ times. Therefore $$\operatorname{cr}(G) \le \binom m2.$$
• Each line yields at least $k-1$ edges, and because $k\ge 2$ we have $k-1 \ge \frac k2$. Therefore $e$, the number of edges, satisfies $$e \ge \frac12 mk.$$
• By the crossing number inequality (as stated on Wikipedia), one of the following holds: $$e \le 7n \quad \text{or} \quad \operatorname{cr}(G) \ge \frac{e^3}{29n^2}.$$

Some algebraic manipulation with the two cases of the inequality should tell you that either $m \le \frac{14 n}{k}$ or $m \le \frac{116n^2}{k^3}$. In the first case, we also need to use the condition $k \le \sqrt n$ to obtain a bound of the form we want.