Erdős Problem #589

Erdős Problem 589 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/589.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT.

For $n\ge 1$, define $g(n)$ (called $g$ in the problem statement) to be the largest integer with the property:

For every set $P\subset\mathbb{R}^2$ of $n$ points with no four collinear, there exists a subset $Q\subseteq P$ with $|Q|\ge g(n)$ such that no three points of $Q$ are collinear.

Equivalently, $g(n)$ is the minimum, over all $n$-point sets $P$ with no four collinear, of the maximum size of a subset in general position (no three collinear).

Question: estimate the growth rate of $g(n)$.

QUICK LITERATURE/CONTEXT CHECK.

I will not use any literature beyond what is explicitly quoted in the problem statement (greedy $\gg n^{1/2}$, upper bound $o(n)$ via density Hales--Jewett, and improvements by Füredi and Balogh--Solymosi).

ATTACK PLAN.

Proof-track ideas. $1$ Model collinear triples as a 3-uniform hypergraph and bound the independence number from below using probabilistic or greedy methods; "no four collinear" should translate to a linearity property of the hypergraph. $2$ Use combinatorial geometry incidence bounds to control the number of collinear triples and thus improve the hypergraph bound.

Disproof/upper-bound ideas. $1$ Seek constructions with many collinear triples arranged so that every large subset contains a triple (dense 3-uniform hypergraphs realizable by point-line incidences).

Here I only re-derive the classical $\Omega(\sqrt n)$-type lower bound in a self-contained way.

WORK.

Lemma 589.1 (hypergraph formulation; linearity from "no four collinear"). Let $P$ be a set of $n$ points in $\mathbb{R}^2$ with no four collinear. Define a 3-uniform hypergraph $\mathcal{H}(P)$ on vertex set $P$ whose hyperedges are the collinear triples of points: \[ E(\mathcal{H}(P)):=\{\{a,b,c\}\subseteq P: a,b,c \text{ are distinct and collinear}\}. \] Then:

(a) A subset $Q\subseteq P$ has no three collinear if and only if $Q$ is an independent set in $\mathcal{H}(P)$ (i.e. $Q$ contains no hyperedge).

(b) $\mathcal{H}(P)$ is linear: any two distinct hyperedges intersect in at most one vertex. Equivalently, any unordered pair of vertices belongs to at most one hyperedge.

Proof. (a) By definition, a hyperedge is exactly a collinear triple in $P$. Thus $Q$ contains a collinear triple if and only if $Q$ contains a hyperedge, i.e. is not independent.

(b) Suppose two distinct hyperedges shared two vertices $a,b$. Then there exist distinct points $c\ne d$ such that $\{a,b,c\}$ and $\{a,b,d\}$ are hyperedges. That means $a,b,c$ are collinear and $a,b,d$ are collinear. But the line through $a$ and $b$ is unique, so $c$ and $d$ are also on that same line, giving four collinear points $a,b,c,d$, contradicting the hypothesis. Therefore any two hyperedges intersect in at most one vertex. $\square$

Lemma 589.2 (probabilistic lower bound on independent sets in linear 3-hypergraphs). Let $\mathcal{H}$ be any 3-uniform hypergraph on $n$ vertices with $m$ hyperedges. Then for any $p\in[0,1]$ there exists an independent set of size at least \[ pn - p^3 m. \] In particular, if $\mathcal{H}$ is linear then $m\le \binom{n}{2}/3$, and choosing $p=n^{-1/2}$ yields an independent set of size at least \[ n^{1/2}-\frac{1}{3}n^{1/2}=\frac{2}{3}\,n^{1/2}. \] Consequently, for every $P\subset\mathbb{R}^2$ with $|P|=n$ and no four collinear, there exists $Q\subseteq P$ with no three collinear and \[ |Q|\ge \frac{2}{3}\sqrt{n}. \]

Proof. Select a random subset $S$ of the vertex set by including each vertex independently with probability $p$. Then $\mathbb{E}|S|=pn$. Let $X$ be the number of hyperedges fully contained in $S$. Each hyperedge is contained in $S$ with probability $p^3$, hence $\mathbb{E}X=p^3 m$.

From $S$, construct $S'$ by deleting, for each hyperedge contained in $S$, one arbitrary vertex of that hyperedge (if multiple hyperedges choose the same vertex to delete, delete it once). Then $S'$ is independent (because every hyperedge in $S$ had at least one vertex removed), and \[ |S'|\ge |S|-X. \] Taking expectations, \[ \mathbb{E}|S'|\ge \mathbb{E}|S|-\mathbb{E}X = pn - p^3 m. \] Therefore there exists at least one outcome of the random choice for which $|S'|\ge pn-p^3 m$, proving the first statement.

Now assume $\mathcal{H}$ is linear. Each hyperedge contains exactly $3$ unordered vertex-pairs, and linearity implies that no unordered pair lies in more than one hyperedge. Hence $3m\le \binom{n}{2}$, i.e. $m\le \binom{n}{2}/3$. Choosing $p=n^{-1/2}$ gives \[ pn-p^3 m \ge \sqrt n - n^{-3/2}\cdot \frac{n(n-1)}{6} = \sqrt n - \frac{n-1}{6\sqrt n} \ge \frac{2}{3}\sqrt n \] for all $n\ge 1$ (one may check the inequality directly).

Finally, apply Lemma 589.1: for a point set $P$ with no four collinear, the hypergraph $\mathcal{H}(P)$ is linear, and an independent set is exactly a subset with no three collinear. Thus $g(n)\ge (2/3)\sqrt n$. $\square$

Fast reality check (plugging small $n$).

The bound from Lemma 589.2 gives $g(9)\ge 2$, $g(16)\ge 2$, $g(25)\ge 3$, $g(36)\ge 4$. These are very weak but consistent with the trivial constraints.

VERIFICATION.

Lemma 589.1. The key point is uniqueness of the line through two distinct points. Linearity of the hypergraph is exactly where "no four collinear" is used.

Lemma 589.2. The deletion argument is valid because deleting at least one vertex from each hyperedge in $S$ guarantees no hyperedge remains fully contained. The expectation bound is one-sided but sufficient for existence. The linearity bound $3m\le \binom{n}{2}$ is rigorous.

FINAL.

UNRESOLVED

(i) Strongest proved partial result: $g(n)\ge \frac{2}{3}\sqrt n$ for all $n$, via the linear 3-uniform hypergraph formulation and a probabilistic independent-set bound (Lemmas 589.1--589.2). This recovers (up to constants) the classical greedy $\gg \sqrt n$ lower bound mentioned in the problem statement.

(ii) First gap (crisp): improve the lower bound beyond $\Theta(\sqrt n)$ (e.g. to $\Omega(\sqrt n\log n)$ as in the problem statement) using only fully justified steps, or alternately give a new explicit construction showing an upper bound $o(n)$ without importing density Hales--Jewett.

(iii) Top 3 next moves: 1. Bound the number of collinear triples $m$ in $\mathcal{H}(P)$ more sharply using planar incidence bounds under "no four collinear", then optimize $p$ in Lemma 589.2 to improve $|Q|$. 2. Replace the simple "delete one per hyperedge" argument by a refined nibble/alteration to reduce over-deletion when hyperedges overlap. 3. Computation: for small $n$ search for point sets (e.g. integer grids with perturbations) maximizing the number of 3-point lines and measure the largest general-position subset size to guess extremal behavior.

(iv) Minimal counterexample structure (to any conjectured linear lower bound): would be a point set with no four collinear but with so many 3-point lines that every subset of size $\varepsilon n$ necessarily contains a collinear triple. Combinatorially, this corresponds to a linear 3-uniform hypergraph on $n$ vertices with very small independence number, and geometrically it would require an incidence structure approaching a dense linear 3-design realizable in $\mathbb{R}^2$.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT.

For $n\ge 1$, define $g(n)$ (called $g$ in the problem statement) to be the largest integer with the property:

For every set $P\subset\mathbb{R}^2$ of $n$ points with no four collinear, there exists a subset $Q\subseteq P$ with $|Q|\ge g(n)$ such that no three points of $Q$ are collinear.

Equivalently, $g(n)$ is the minimum, over all $n$-point sets $P$ with no four collinear, of the maximum size of a subset in general position (no three collinear).

Question: estimate the growth rate of $g(n)$.

QUICK LITERATURE/CONTEXT CHECK.

I will not use any literature beyond what is explicitly quoted in the problem statement (greedy $\gg n^{1/2}$, upper bound $o(n)$ via density Hales--Jewett, and improvements by Füredi and Balogh--Solymosi).

ATTACK PLAN.

Proof-track ideas. $1$ Model collinear triples as a 3-uniform hypergraph and bound the independence number from below using probabilistic or greedy methods; "no four collinear" should translate to a linearity property of the hypergraph. $2$ Use combinatorial geometry incidence bounds to control the number of collinear triples and thus improve the hypergraph bound.

Disproof/upper-bound ideas. $1$ Seek constructions with many collinear triples arranged so that every large subset contains a triple (dense 3-uniform hypergraphs realizable by point-line incidences).

Here I only re-derive the classical $\Omega(\sqrt n)$-type lower bound in a self-contained way.

WORK.

Lemma 589.1 (hypergraph formulation; linearity from "no four collinear"). Let $P$ be a set of $n$ points in $\mathbb{R}^2$ with no four collinear. Define a 3-uniform hypergraph $\mathcal{H}(P)$ on vertex set $P$ whose hyperedges are the collinear triples of points: \[ E(\mathcal{H}(P)):=\{\{a,b,c\}\subseteq P: a,b,c \text{ are distinct and collinear}\}. \] Then:

(a) A subset $Q\subseteq P$ has no three collinear if and only if $Q$ is an independent set in $\mathcal{H}(P)$ (i.e. $Q$ contains no hyperedge).

(b) $\mathcal{H}(P)$ is linear: any two distinct hyperedges intersect in at most one vertex. Equivalently, any unordered pair of vertices belongs to at most one hyperedge.

Proof. (a) By definition, a hyperedge is exactly a collinear triple in $P$. Thus $Q$ contains a collinear triple if and only if $Q$ contains a hyperedge, i.e. is not independent.

(b) Suppose two distinct hyperedges shared two vertices $a,b$. Then there exist distinct points $c\ne d$ such that $\{a,b,c\}$ and $\{a,b,d\}$ are hyperedges. That means $a,b,c$ are collinear and $a,b,d$ are collinear. But the line through $a$ and $b$ is unique, so $c$ and $d$ are also on that same line, giving four collinear points $a,b,c,d$, contradicting the hypothesis. Therefore any two hyperedges intersect in at most one vertex. $\square$

Lemma 589.2 (probabilistic lower bound on independent sets in linear 3-hypergraphs). Let $\mathcal{H}$ be any 3-uniform hypergraph on $n$ vertices with $m$ hyperedges. Then for any $p\in[0,1]$ there exists an independent set of size at least \[ pn - p^3 m. \] In particular, if $\mathcal{H}$ is linear then $m\le \binom{n}{2}/3$, and choosing $p=n^{-1/2}$ yields an independent set of size at least \[ n^{1/2}-\frac{1}{3}n^{1/2}=\frac{2}{3}\,n^{1/2}. \] Consequently, for every $P\subset\mathbb{R}^2$ with $|P|=n$ and no four collinear, there exists $Q\subseteq P$ with no three collinear and \[ |Q|\ge \frac{2}{3}\sqrt{n}. \]

Proof. Select a random subset $S$ of the vertex set by including each vertex independently with probability $p$. Then $\mathbb{E}|S|=pn$. Let $X$ be the number of hyperedges fully contained in $S$. Each hyperedge is contained in $S$ with probability $p^3$, hence $\mathbb{E}X=p^3 m$.

From $S$, construct $S'$ by deleting, for each hyperedge contained in $S$, one arbitrary vertex of that hyperedge (if multiple hyperedges choose the same vertex to delete, delete it once). Then $S'$ is independent (because every hyperedge in $S$ had at least one vertex removed), and \[ |S'|\ge |S|-X. \] Taking expectations, \[ \mathbb{E}|S'|\ge \mathbb{E}|S|-\mathbb{E}X = pn - p^3 m. \] Therefore there exists at least one outcome of the random choice for which $|S'|\ge pn-p^3 m$, proving the first statement.

Now assume $\mathcal{H}$ is linear. Each hyperedge contains exactly $3$ unordered vertex-pairs, and linearity implies that no unordered pair lies in more than one hyperedge. Hence $3m\le \binom{n}{2}$, i.e. $m\le \binom{n}{2}/3$. Choosing $p=n^{-1/2}$ gives \[ pn-p^3 m \ge \sqrt n - n^{-3/2}\cdot \frac{n(n-1)}{6} = \sqrt n - \frac{n-1}{6\sqrt n} \ge \frac{2}{3}\sqrt n \] for all $n\ge 1$ (one may check the inequality directly).

Finally, apply Lemma 589.1: for a point set $P$ with no four collinear, the hypergraph $\mathcal{H}(P)$ is linear, and an independent set is exactly a subset with no three collinear. Thus $g(n)\ge (2/3)\sqrt n$. $\square$

Fast reality check (plugging small $n$).

The bound from Lemma 589.2 gives $g(9)\ge 2$, $g(16)\ge 2$, $g(25)\ge 3$, $g(36)\ge 4$. These are very weak but consistent with the trivial constraints.

VERIFICATION.

Lemma 589.1. The key point is uniqueness of the line through two distinct points. Linearity of the hypergraph is exactly where "no four collinear" is used.

Lemma 589.2. The deletion argument is valid because deleting at least one vertex from each hyperedge in $S$ guarantees no hyperedge remains fully contained. The expectation bound is one-sided but sufficient for existence. The linearity bound $3m\le \binom{n}{2}$ is rigorous.

FINAL.

UNRESOLVED

(i) Strongest proved partial result: $g(n)\ge \frac{2}{3}\sqrt n$ for all $n$, via the linear 3-uniform hypergraph formulation and a probabilistic independent-set bound (Lemmas 589.1--589.2). This recovers (up to constants) the classical greedy $\gg \sqrt n$ lower bound mentioned in the problem statement.

(ii) First gap (crisp): improve the lower bound beyond $\Theta(\sqrt n)$ (e.g. to $\Omega(\sqrt n\log n)$ as in the problem statement) using only fully justified steps, or alternately give a new explicit construction showing an upper bound $o(n)$ without importing density Hales--Jewett.

(iii) Top 3 next moves: 1. Bound the number of collinear triples $m$ in $\mathcal{H}(P)$ more sharply using planar incidence bounds under "no four collinear", then optimize $p$ in Lemma 589.2 to improve $|Q|$. 2. Replace the simple "delete one per hyperedge" argument by a refined nibble/alteration to reduce over-deletion when hyperedges overlap. 3. Computation: for small $n$ search for point sets (e.g. integer grids with perturbations) maximizing the number of 3-point lines and measure the largest general-position subset size to guess extremal behavior.

(iv) Minimal counterexample structure (to any conjectured linear lower bound): would be a point set with no four collinear but with so many 3-point lines that every subset of size $\varepsilon n$ necessarily contains a collinear triple. Combinatorially, this corresponds to a linear 3-uniform hypergraph on $n$ vertices with very small independence number, and geometrically it would require an incidence structure approaching a dense linear 3-design realizable in $\mathbb{R}^2$.