Comparability sets in $[N]^3$: is $|S|\le N^{2-\delta}$? (Ben Green Problem 88, Gowers-Long)
Statement
Call two distinct points $s,s'\in[N]^3$ (where $[N]=\{1,\dots,N\}$) comparable if $s-s'$ has either at least two strictly positive coordinates or at least two strictly negative coordinates. Let $S\subseteq[N]^3$ be a set in which every two distinct points are comparable. Is there an absolute constant $\delta>0$ with $|S|\le N^{2-\delta}$ for all $N$? Equivalently, bound the maximum independent set of the explicit graph on $[N]^3$ joining $x,y$ iff they are NOT comparable.
Acceptance. ADVANCES: exact values of the maximum comparability-set size $\alpha(N)$ (resp. the modular $\mathbb{F}_p^3$ analogue) for small $N,p$, each certified by an optimal independent set plus a matching LP/ILP dual bound (a reproducible solver certificate), extending the extremal data and pinning the exponent trend. FULLY RESOLVES: a proof that $|S|\le N^{2-\delta}$ for some explicit $\delta>0$ (or a construction with $|S|\ge N^{2-o(1)}$ beating every layer bound, showing no such $\delta$), and/or the same for the modular version. Provide the extremal sets and the verification/solver scripts.
Background
Problem 88 of Ben Green's 'Open Problems' manuscript (updated Dec 2025). It originates with W. T. Gowers & J. Long, 'The length of an $s$-increasing sequence of $r$-tuples' (arXiv:1609.08688; Combin. Probab. Comput.), motivated by a question of Po-Shen Loh. The related INCREASING-sequence version was handled by Gowers-Long, whose argument essentially uses that the sequence is increasing rather than merely comparable; the COMPARABILITY version stated here is open, and Green notes it sits just below the density threshold where the standard Delsarte/spectral bound bites. A single 'layer' gives the trivial $|S|=O(N^2)$; breaking $N^{2-\delta}$ is the goal. Green also states a symmetric modular analogue in $\mathbb{F}_p^3$ (six explicit comparability classes $S$; if $A-A$ avoids $S$, is $|A|\le p^{2-\delta}$?), which has more symmetry. An attacker needs: (i) exact maximum-independent-set solvers (ILP/SAT/branch-and-bound) for small $N$ (and small $p$ in the modular version) to compute $\alpha(N)$ and fit the exponent; (ii) a spectral / LP (weighted Delsarte) relaxation with a hand-crafted dual certificate to prove an $N^{2-\delta}$ bound in the Cayley-graph modular case.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Ben Green, 100 Open Problems (Problem 88) | paper |
| REF-02 | The length of an s-increasing sequence of r-tuples (Gowers-Long) | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.