Collinear Grid Triples and Rigid Bipartite Unit Distance Graphs

Definitions and mathematical statement

For a positive integer $n$, let $G_n=\{1,\ldots,n\}^3\subset{\mathbb{R}}^3$. For $S\subseteq G_n$, define \[ c_3(S)=\left|\left\{U\subseteq S:\ |U|=3\text{ and }U\text{ lies on a single affine line in }{\mathbb{R}}^3\right\}\right|. \] Thus triples consist of three distinct points and are counted without ordering; a line containing $k$ points of $S$ contributes $\binom{k}{3}$ triples. For an integer $m$ with $0\le m\le n^3$, set \[ M(n,m)=\min_{\substack{S\subseteq G_n\\|S|=m}}c_3(S). \] The grid problem asks to determine \[ M\left(n,n^{3-s}\right), \] whenever $n^{3-s}$ is an integer in $[0,n^3]$. The source does not specify the domain or range of $s$, whether $s$ is fixed as $n$ grows, or a rounding convention when $n^{3-s}$ is not an integer. Consequently this expression is stated only for admissible exact cardinalities. It is also unresolved whether the intended answer is an exact minimum or a sharp asymptotic estimate. The unordered, distinct-point convention above makes explicit the usual meaning of a collinear triple, which the supplied record does not define separately.

The original statement additionally asks: Find a rigid bipartite unit-distance graph. Bipartiteness means that the vertex set admits a partition $V=A\sqcup B$ such that every edge joins a vertex of $A$ to a vertex of $B$. For a specified Euclidean dimension $d$, a unit-distance realization would assign points $p_v\in{\mathbb{R}}^d$ satisfying \[ \|p_u-p_v\|_2=1\qquad\text{for every }\{u,v\}\in E. \] The source does not specify $d$, finiteness, distinctness requirements for the assigned points, whether nonadjacent vertices may also be at unit distance, or the intended notion of rigidity. In particular, rigidity of a particular realization, generic rigidity of a graph, infinitesimal rigidity, and global rigidity cannot be identified without further hypotheses. This secondary request is therefore retained as an unresolved formulation rather than assigned an invented rigidity predicate. It appears in the original statement and title but is omitted from the cleaned statement.

Short English statement

Determine the least number of unordered collinear triples of distinct points in an $n\times n\times n$ integer grid subset containing exactly $n^{3-s}$ points, whenever that cardinality is admissible. The allowed parameter range and intended precision of the answer are unspecified. The original record also asks for a rigid bipartite unit-distance graph, but omits the dimension and rigidity convention needed to make that request precise.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003477$, source problem code catalogue entry, titled "Collinear Grid Triples and Rigid Bipartite Unit Distance Graphs." Collection: Oberwolfach Reports Open Problems. The proposed year is recorded as 2017; no individual proposer is supplied.
• Supplied report citation: Discrete Geometry (2018), Oberwolfach Reports, DOI 10.4171/owr/2017/19, pp. 1135--1205. https://doi.org/10.4171/owr/2017/19. The supplied background describes these reports as documenting mathematical workshops and their open-problem discussions. The citation is retained as supplied; the report and its problem attribution have not been independently verified.
• Supplied literature reference: "Balogh and Solymosi on collinear triples." https://arxiv.org/abs/1704.05089.
• Supplied literature reference: "Roche-Newton on grid constructions." https://arxiv.org/abs/2607.25742.
• Supplied literature reference: "Kaszanitzky and collaborators on rigid unit frameworks." https://arxiv.org/abs/1808.04005.
• Literature assessment dated exactly 2026-08-21: supplied dated curation, not independently verified. The record labels the problem "partially solved" and reports matching-scale grid constructions up to logarithmic factors with an unresolved sharp lower-bound issue, together with affirmative rigid-framework constructions for the separate bipartite unit-distance question. The background explicitly calls this a dated literature triage derived from supplied OWR curation and requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and says that mathematical content was preserved while notation, typography, and sentence structure were repaired. These are supplied editorial assertions, not independent verification of this draft or of either mathematical question.