Ordinary-line counts under restricted collinearity

An ordinary line through a finite planar point set contains exactly two of its points. How many ordinary lines can a set have while restricting collinearity and forbidding cliques in the graph formed by ordinary-line pairs?

Why it matters and what counts as progress

Why it matters: Quadratic constructions test the expectation that these restrictions force a subquadratic ordinary-line count.

What counts as progress: Constructions or upper bounds for the extremal count Fᵣ,ₖ(n), with the collinearity and forbidden-clique parameters specified, including r=3 and k=4.

How the problem developed

1984 · Open question [1]
Paul Erdős Asked whether the threshold forcing an ordinary-line clique under a bounded-collinearity condition could be subquadratic or even linear.
9 Apr 2026 · Counterexample [2]
Boris Alexeev, Moe Putterman, Mehtaab Sawhney, Mark Sellke and Gregory Valiant Gave, for fixed r≥3 and k≥4, n-point sets with no k collinear points, no ordinary-line Kᵣ, and at least n²/12−(10/3)n ordinary lines for n≥72.

AI contribution

Short proofs in combinatorics, probability and number theory II

Boris Alexeev, Moe Putterman, Mehtaab Sawhney, Mark Sellke, Gregory Valiant

For integers r≥3, k≥4 and n≥72, the maximum ordinary-line count Fᵣ,ₖ(n) is at least n²/12−(10/3)n. The elliptic-curve construction has no four collinear points and a bipartite ordinary-line graph.

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull