Problem 588 — Visual explainer (undergrad)
==========================================

Problem statement
---------------
Let $f_k(n)$ be minimal such that if $n$ points in $\mathbb{R}^2$ have no $k+1$ points on a line then there must be at most $f_k(n)$ many lines containing at least $k$ points. Is it true that\[f_k(n)=o(n^2)\]for $k\geq 4$?

Picture
-------
Many points on a line:

o---o---o---o---o
\
 o   o      o

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: incidence geometry / combinatorial geometry.

Notation (if it appears above)
-----------------------------
- `o(g(n))` means "grows strictly smaller than g(n)" (ratio → 0 as n→∞).

Benchmarks / known results (from comments)
----------------------------------------
- A generalisation of [101] (which asks about $k=4$).
- The restriction to $k\geq 4$ is necessary since Sylvester has shown that
  $f_3(n)= n^2/6+O(n)$.
- (See also Burr, Gr\"{u}nbaum, and Sloane and F\"{u}redi and Pal\'{a}sti for
  constructions which show that $f_3(n)\geq(1/6+o(1))n^2$.) For $k\geq 4$,
  K\'{a}rteszi proved\[f_k(n)\gg_k n\log n\](resolving a conjecture of
  Erd\H{o}s that $f_k(n)/n\to \infty$).