ESₗ(n) joint dependence on ℓ
Open Problem (Introduction) · arXiv:2405.03455
Status open high confidence
The paper establishes $(3\ell-1)\cdot 2^{n-5} < ES_{\ell}(n) < \ell^{2}\cdot 2^{n+C\sqrt{n\log n}}$, leaving a gap between the linear lower bound and the quadratic upper bound in $\ell$. No follow-up paper resolving the correct joint dependence on $\ell$ was found in the indexed literature. The paper appeared in Computational Geometry, vol. 131 (2026).
Reviewer notes. No follow-up paper resolving the ell-dependence question was found after three targeted searches and two fetches. The related paper arXiv:2409.03122 (Furukawa, 'Happy ending or many concurrent lines') studies a dual line-version of the problem and does not address the point-version open problem. The paper itself was published in Computational Geometry, vol. 131 (2026), article 102218, without revision of the open problem.
Context
The paper establishes that $(3\ell-1)\cdot 2^{n-5} < ES_{\ell}(n) < \ell^{2}\cdot 2^{n+C\sqrt{n\log n}}$, leaving a gap in the dependence on $\ell$. In the regime where $n$ is fixed and $\ell\to\infty$, the cups-caps theorem gives $ES_{\ell}(n)=O(\ell)$, which is best possible up to constants, but the general joint dependence on both parameters remains open.
Notes. Stated in running prose at the end of the introduction: "It remains an interesting open problem to determine the correct dependence of $ES_{\ell}(n)$ on $\ell$."
Source paper
Big line or big convex polygon
David Conlon, Jacob Fox, Xiaoyu He, Dhruv Mubayi, Andrew Suk, Jacques Verstraete · 2024-05-06
https://arxiv.org/abs/2405.03455