Problem 589

../

claims/: The 2 claim pages of Problem 589, one per claimant's result; the problem's standing derives from them.

---

Statement. Let $g(n)$ be maximal such that in any set of $n$ points in $\mathbb{R}^2$ with no four points on a line there exists a subset on $g(n)$ points with no three points on a line. Estimate $g(n)$.

Status. Open, in the site's label. The accepted partial claims Füredi 1991 and [[problems/discrete_geometry/E0589/claims/2017_04_17_balogh_solymosi|Balogh and Solymosi 2017]] give $c\sqrt{n\log n}<g(n)\le n^{5/6+o(1)}$; the order of $g(n)$ is undetermined. Furstenberg and Katznelson's density Hales--Jewett theorem [FuKa91], which Füredi applies, says nothing about $g(n)$ itself and has no claim page.

Source. erdosproblems.com/589, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #589, https://www.erdosproblems.com/589.

References.

• [BaSo18] Balogh, József and Solymosi, József, On the number of points in general position in the plane. Discrete Anal. (2018), Paper No. 16, 20.
• [Fu91b] Füredi, Zoltán, Maximal independent subsets in Steiner systems and in planar sets. SIAM J. Discrete Math. (1991), 196-199.
• [FuKa91] Furstenberg, H. and Katznelson, Y., A density version of the Hales-Jewett Theorem. Journal d'Analyse Mathématique (1991), 64-119.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• balogh_2018_number_points_general_position_plane
• erdos_1984_research_problems
• erdos_1984_research_problems / problem_p102_general_position_subsets
• furedi_1991_maximal_independent_subsets_steiner_systems_planar_sets
• furedi_1991_maximal_independent_subsets_steiner_systems_planar_sets / theorem_1_1