Erdős Problem #846

Erdős Problem 846

Statement and result.

The points.

Exactly which triples are collinear.

For pairs $ij,ik,jk$, write $a=t_i,b=t_j,c=t_k$. All three points satisfy \[ y=(a+b+c)x-(ab+ac+bc), \] as direct substitution shows. Thus triangle triples are collinear.

For the converse, three distinct edges of a simple graph have one of five forms: a triangle, a three-edge star, a three-edge path, a two-edge path together with a disjoint edge, or three disjoint edges. Collinearity is the vanishing of the polynomial determinant \[ D=\det\begin{pmatrix}1&x_1&y_1\\1&x_2&y_2\\1&x_3&y_3\end{pmatrix}. \] For the four nontriangle forms this is a nonzero polynomial. Here is an explicit certificate: substitute $(t_1,\ldots,t_6)=(0,1,3,7,11,13)$, using only the coordinates needed in each row. In the stated edge order the determinants are \[ \begin{array}{c|r} \text{index pairs}&D\\ \hline 12,13,14&48\\ 12,23,34&126\\ 12,13,45&356\\ 12,34,56&2094 \end{array} \] These evaluations prove that the four determinant polynomials are not identically zero. Algebraic independence then prevents them from vanishing at the chosen $t_i$. Relabelling indices handles every triple of each type, proving the claim.

Every finite subset has a large general-position subset.

No finite partition works.

For completeness, the needed finite multicolour Ramsey fact follows by a short induction. Let $R_1=3$ and \[ R_r=r(R_{r-1}-1)+2. \] In an $r$-edge-colouring of $K_{R_r}$, some vertex has at least $R_{r-1}$ neighbours joined to it in one colour. An edge of that colour among those neighbours gives a triangle with the vertex; if no such edge exists, their complete graph uses at most $r-1$ colours and the induction hypothesis applies. Thus every finite $r$ admits a finite triangle Ramsey bound. Restricting our infinite colouring to its first $R_r$ vertices is a contradiction.

Attribution and assessment.

Completion rate estimate: 100%.

Let $A\subset \mathbb{R}^2$ be an infinite set for which there exists some $\epsilon>0$ such that in any subset of $A$ of size $n$ there are always at least $\epsilon n$ with no three on a line. Is it true that $A$ is the union of a finite number of sets where no three are on a line? A problem of Erdős, Nešetřil, and Rödl. See also [774] and [847] .

1) “FORMAL RESTATEMENT”

Fix an infinite set $A\subset\mathbb{R}^2$. Assume:

$\exists\,\epsilon>0$ such that $\forall n\in\mathbb{N}_{\ge 1}$ and $\forall S\subset A$ with $|S|=n$, there exists a subset $T\subset S$ with \[ |T|\ge \epsilon n \] and $T$ has no three collinear points, i.e. for every affine line $\ell\subset\mathbb{R}^2$ we have $|T\cap \ell|\le 2$.

Question: Does it follow that there exists an integer $m\ge 1$ and a covering \[ A = A_1\cup\cdots\cup A_m \] with each $A_i\subset\mathbb{R}^2$ having no three collinear points (equivalently: a coloring of $A$ with $m$ colors such that no line contains three points of the same color)?

Conventions/edge cases: - A “subset of size $n$” means an $n$-element subset. - If $A$ itself has no three collinear points then the answer is “yes” with $m=1$. - The hypothesis forces $0<\epsilon\le 1$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem statement provides no theorems to use directly, only cross-references to other Erdős problems. In this solution write-up I do not invoke external literature beyond what is explicitly stated in the problem text.

3) “ATTACK PLAN”

Proof-track ideas: - View collinear triples in $A$ as edges of a $3$-uniform hypergraph $\mathcal{H}(A)$. The hypothesis says every induced subhypergraph on $n$ vertices has an independent set of size $\ge \epsilon n$. Try to deduce bounded chromatic number of $\mathcal{H}(A)$. - Use geometry: the hypothesis forces a uniform bound on the number of points of $A$ on any line. Try to leverage bounded “line multiplicity” to obtain a finite coloring.

Disproof/construction ideas: - Try to build an infinite set $A$ as a union of finite “blocks” $B_j$ that are far apart so that the hereditary independent-set condition holds with a fixed $\epsilon$, while the required number of colors for each $B_j$ tends to infinity.

Best current path in this write-up: extract unavoidable structural consequences (line-multiplicity bounds) and show what they do and do not give (notably an $O(\log n)$ coloring bound for finite subsets, but no uniform bound).

4) “WORK”

FAST REALITY CHECK (small $n$): - If some 3-point subset of $A$ is collinear, then for $n=3$ the largest subset with no three collinear has size $2$, so the hypothesis forces $3\epsilon\le 2$, i.e. $\epsilon\le 2/3$.

Lemma 846.1 (Finite union $\Rightarrow$ linear-sized general position subset). If $A=\bigcup_{i=1}^m A_i$ where each $A_i$ has no three collinear points, then the hypothesis holds with $\epsilon=1/m$.

Proof. Let $S\subset A$ be any finite subset of size $n$. Then $S=\bigcup_{i=1}^m (S\cap A_i)$. By the pigeonhole principle there exists $i$ with \[ |S\cap A_i|\ge n/m. \] Let $T:=S\cap A_i$. Then $|T|\ge (1/m)n$ and $T\subset A_i$ has no three collinear points by assumption on $A_i$. $\square$

Lemma 846.2 (Uniform bound on points of $A$ per line). Assume the hypothesis with parameter $\epsilon>0$. Then every affine line $\ell\subset\mathbb{R}^2$ satisfies \[ |A\cap \ell|\le \left\lfloor \frac{2}{\epsilon}\right\rfloor. \] In particular $A$ contains no infinite collinear subset.

Proof. Suppose for contradiction that some line $\ell$ contains $M$ points of $A$ with $M>2/\epsilon$. Let $S\subset A\cap\ell$ be any subset of size $n:=M$ (so $S$ consists of $M$ collinear points). Any subset $T\subset S$ with no three collinear points can contain at most $2$ points of $\ell$, hence must satisfy $|T|\le 2$. But the hypothesis applied to this $S$ demands a $T$ with $|T|\ge \epsilon n = \epsilon M>2$, a contradiction. Therefore $|A\cap\ell|\le 2/\epsilon$, and since the left side is an integer we obtain the stated floor bound. $\square$

Lemma 846.3 (Logarithmic coloring bound for finite subsets). Assume the hypothesis with parameter $\epsilon>0$. Then for every finite $S\subset A$ with $|S|=n\ge 1$, there exists a partition \[ S = S_1\cup\cdots\cup S_t \] with each $S_j$ having no three collinear points and \[ t \le 1+\left\lceil \frac{\log n}{\log(1/(1-\epsilon))}\right\rceil. \]

Proof. Define $S^{(0)}:=S$. If $S^{(j)}$ is nonempty with $|S^{(j)}|=n_j$, apply the hypothesis to $S^{(j)}$ to obtain a subset $S_{j+1}\subset S^{(j)}$ with $|S_{j+1}|\ge \epsilon n_j$ and no three collinear points. Remove it: set $S^{(j+1)}:=S^{(j)}\setminus S_{j+1}$. Then \[ |S^{(j+1)}| = n_j-|S_{j+1}| \le n_j-\epsilon n_j = (1-\epsilon)n_j. \] Iterating gives $|S^{(t)}|\le (1-\epsilon)^t n$. Choose $t$ minimal such that $(1-\epsilon)^t n<1$. Then $S^{(t)}$ must be empty (it has integer size), so $S$ is the disjoint union of $S_1,\dots,S_t$ and each $S_j$ has no three collinear points.

To bound $t$, the inequality $(1-\epsilon)^t n<1$ is equivalent to \[ t> \frac{\log n}{\log(1/(1-\epsilon))}. \] Thus one may take \[ t = 1+\left\lceil \frac{\log n}{\log(1/(1-\epsilon))}\right\rceil. \] $\square$

5) “VERIFICATION”

- Quantifiers: Lemma 846.2 uses the hypothesis for a subset $S$ contained in a single line; this is allowed because $S\subset A$ is arbitrary. - Boundary cases: if $n=1$ then Lemma 846.3 gives $t\le 1$ and the partition is trivial. - Lemma 846.3 yields only $t=O_\epsilon(\log n)$, which grows with $n$ and therefore does not directly imply a uniform finite $m$ for all of $A$.

6) FINAL

UNRESOLVED (i) Strongest fully proved partial result: Under the hypothesis, every line meets $A$ in at most $\lfloor 2/\epsilon\rfloor$ points (Lemma 846.2), and every finite $n$-point subset of $A$ can be partitioned into $O_\epsilon(\log n)$ sets with no three collinear points (Lemma 846.3). Also, any finite union of no-three-collinear sets satisfies the hypothesis with $\epsilon=1/m$ (Lemma 846.1). (ii) First gap (crisp): Prove (or disprove) that the hypothesis forces a partition of the entire infinite $A$ into at most $m=m(\epsilon)$ subsets with no three collinear points (equivalently: bounded chromatic number of the collinearity $3$-uniform hypergraph), i.e. upgrade the $O(\log n)$ bound of Lemma 846.3 to an $O(1)$ bound independent of $n$. (iii) Top 3 next moves: 1. Try to construct finite point sets $S\subset\mathbb{R}^2$ for which every subset contains a general-position subset of size at least $\epsilon$ times its size, but the minimum number of colors needed to avoid monochromatic collinear triples tends to infinity; then separate such blocks far apart to build an infinite counterexample. 2. Attempt a geometric structure theorem: show that bounded line multiplicity together with the hereditary linear-independent-set condition implies bounded chromatic number for the collinearity hypergraph. 3. Compute/search: for small finite configurations with bounded points per line, brute-force the maximum ratio $\alpha(S)/|S|$ (largest general-position subset) versus the chromatic number (minimum colors to avoid monochromatic collinear triples) to see whether a counterexample pattern emerges. (iv) Minimal counterexample structure: An infinite $A$ with a uniform bound on $|A\cap\ell|$ for every line, built from finite “blocks” $B_j$ whose internal collinearity constraints force chromatic number $\chi(B_j)\to\infty$, while still ensuring that every subset of $B_j$ has an independent set of size $\ge \epsilon|\cdot|$.