Collinear-Triple-Free Sets in Random Grids

Definitions and mathematical statement

For a positive integer $n$, write $[n]=\{1,\ldots,n\}$ and regard $[n]^2$ as a subset of the Euclidean plane ${\mathbb{R}}^2$. For $p\in[0,1]$, let $R_{n,p}\subseteq[n]^2$ be random, with each point retained independently with probability $p$. A set $S\subseteq[n]^2$ is collinear-triple-free if no three distinct points of $S$ lie on a common affine line in ${\mathbb{R}}^2$. Equivalently, for all pairwise distinct $(x_1,y_1),(x_2,y_2),(x_3,y_3)\in S$, \[ \det\begin{pmatrix} x_1&y_1&1\\ x_2&y_2&1\\ x_3&y_3&1 \end{pmatrix}\ne0. \] Define the random variable \[ \alpha([n]^2,p)=\max\left\{|S|:S\subseteq R_{n,p},\ S\text{ is collinear-triple-free}\right\}. \] The empty set is admissible, so this maximum is defined for every realization, including when $R_{n,p}=\varnothing$. The definition includes the boundary cases $p=0$ and $p=1$.

Problem (source Problem 2). Characterize $\alpha([n]^2,p)$ as a function of the grid size $n$ and retention probability $p$.

Unresolved scope. The supplied source does not specify whether a characterization means an exact distribution, expectation, concentration, asymptotic order, or sharp asymptotic bounds. It also specifies neither a regime for $p$, possibly depending on $n$, nor a probability or error criterion for an asymptotic assertion. Thus the random variable is precisely defined here, but the requested characterization remains an open-ended research target.

The supplied report context motivates the grid problem by a finite-field analogue: it describes using a hypergraph container lemma and balanced supersaturation of collinear triples, obtained through pseudorandomness of the point--line incidence bipartite graph of the finite-field plane. These are contextual descriptions of the finite-field work, not hypotheses or asserted conclusions for the grid problem.

Short English statement

Independently keep each point of an $n$-by-$n$ integer grid with probability $p$. Characterize the largest number of retained points that can be selected with no three on a line. This maximum is random; the source leaves the desired type of characterization and parameter regime unspecified.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $30005808$, title Collinear-Triple-Free Sets in Random Grids, exact source code catalogue entry. The supplied record attributes the problem to the Oberwolfach Reports collection, gives proposed year 2024, and names no individual proposer.
• Discrete Geometry (2024), Oberwolfach Reports, pp. 137--202, DOI 10.4171/owr/2024/3, source Problem 2. Supplied source and literature link: https://doi.org/10.4171/owr/2024/3.
• Supplied literature assessment dated 2026-08-22: the grid characterization is identified as a future direction, the finite-field analogue is described as treated, and no complete grid characterization is cited. The supplied status is open. This is supplied dated curation, not an independently verified literature assessment; the record itself requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that it was reconstructed and checked against the official Oberwolfach report. These are supplied verification claims, not independent verification by this draft.