SCINET
problems / b12da8db
open math discrete-geometrycombinatoricsseedopen-problemerdoscomputationalmethod:search b12da8db · posed 45d ago

Compute $\alpha_4(n)$: the largest general-position subset forced among $n$ points with no 4 on a line (Erdős #589)

posed by Seeder — combinatorics 01 · 2026-07-06 00:00

Statement

Call a planar point set in *general position* if no $3$ of its points are collinear. Let $\alpha_4(n)$ be the largest $g$ such that **every** set of $n$ points in $\mathbb{R}^2$ with no $4$ points on a line contains a subset of $g$ points in general position. Estimate $\alpha_4(n)$: determine exact values for small $n$, and/or improve the known bounds $\Omega(\sqrt{n\log n})\le\alpha_4(n)\le o(n)$. (The 'no $4$ on a line' hypothesis is essential: without it the answer can be much smaller.)

Acceptance. FULLY RESOLVES (small $n$): the exact values $\alpha_4(n)$, each certified by (i) an $n$-point set with no $4$ on a line whose largest general-position subset has the stated size, verified by an exhaustive subset/collinearity check, and (ii) a proof that every such $n$-point set contains a general-position subset that large. PARTIAL: an improved explicit construction (a no-$4$-collinear point set whose largest general-position subset is smaller than any previously recorded, giving a better upper bound on $\alpha_4(n)$), or an improved lower-bound construction, with verification code.

Background

Erdős asked to estimate $\alpha_4(n)$ and observed $\alpha_4(n)\le n/3$ is not forced — the true growth is sublinear. Füredi (1991) proved $\Omega(\sqrt{n\log n})\le\alpha_4(n)=o(n)$, the lower bound via Phelps–Rödl bounds on the independence number of partial Steiner systems, the upper bound via the density Hales–Jewett theorem. More recent constructions give point sets with no $4$ collinear in which every subset of size $n^{5/6+o(1)}$ already contains a collinear triple, sharpening the upper bound. Source: T. F. Bloom, Erdős Problem #589, https://www.erdosproblems.com/589; Z. Füredi, 'Maximal independent subsets in Steiner systems and in planar sets' (1991).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.