---

Claim. Let $g(n)$ be the largest number such that every set of $n$ points in $\mathbb{R}^2$ with no four on a line contains $g(n)$ points with no three on a line, the function of Problem 589 (the paper's $\alpha(n)$). Theorem 1.1 of Z. Füredi, Maximal independent subsets in Steiner systems and in planar sets, states that there is a constant $c>0$ with

$$c\sqrt{n\log n}<g(n)\quad\text{for all }n,\qquad\text{and}\qquad g(n)=o(n).$$

The upper bound comes from Construction 1.1, the sets $S^t$ of $3^t$ integer combinations, with coefficients $0$, $1$ and $2$, of $t$ rationally independent unit vectors: they have no four points on a line, and the density Hales--Jewett theorem of Furstenberg and Katznelson makes every subset of positive density contain the projection of a combinatorial line, a collinear triple, so $g(S^t)=o(3^t)$. The lower bound goes through partial Steiner triple systems: the collinear triples of such a point set form a partial Steiner triple system, and the independence-number bound of Komlós, Pintz and Szemerédi for partial Steiner families of girth at least $5$, in the form of Phelps and Rödl, gives an independent subset of size $\ge c\sqrt{n\log n}$. The upper bound rules out $g(n)\gg n$; the paper sets it against Erdős's remark that every construction then known contains at least $|S|/3$ independent points (p. 196). The site's commentary prints the lower bound as $n^{1/2}\log n$; the paper's bound is $\sqrt{n\log n}$, as Balogh and Solymosi also cite it, and this page uses the paper's bound. The [[../library/discrete_geometry/furedi_1991_maximal_independent_subsets_steiner_systems_planar_sets/_index|source card]] records the paper's results, and the [[../library/discrete_geometry/furedi_1991_maximal_independent_subsets_steiner_systems_planar_sets/theorem_1_1|Theorem 1.1 page]] records the theorem.

Covers. The bounds $c\sqrt{n\log n}<g(n)$ and $g(n)=o(n)$, which together refute $g(n)\gg n$. Not covered: the order of $g(n)$, which is not determined; the upper bound was later improved to $n^{5/6+o(1)}$ by [[problems/discrete_geometry/E0589/claims/2017_04_17_balogh_solymosi|Balogh and Solymosi]].

Depends on. Nothing in this wiki; the claim rests on the cited paper and the density Hales--Jewett theorem it applies.

Acceptance. Refereed: Z. Füredi, Maximal independent subsets in Steiner systems and in planar sets, SIAM J. Discrete Math. 4 (1991), no. 2, 196--199. The site's commentary records the bounds, but the site labels the problem OPEN, so that remark is not acceptance of the problem and the page lists no reviewed evidence. The proof is not compiled in this corpus.

Dating. The page is dated by the issue month in the publisher's record, May 1991; the day is a placeholder.