ESₗ(n) joint dependence on ℓ

AX_erdos_szekeres_collinear_variant_ell_dependence

Source: arXiv:2405.03455 — Big line or big convex polygon

Open Problem (Introduction) · arXiv:2405.03455

arXiv Problem medium confidence— first stated 2024-05-06

Authors: David Conlon, Jacob Fox, Xiaoyu He, Dhruv Mubayi, Andrew Suk, Jacques Verstraete

Status ai-proved high confidence

An alteration argument gives ES_l(n) <= ceil(l(4 ES_n(n))^((n-1)/(n-2))), so the source bound yields a uniform linear-in-l upper bound matching the lower bound in its l-dependence.

Auto-reviewed 2026-08-31 with gpt-5.6-sol.

AI-generated write-up ai-proved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

Problem. Determine the correct dependence of $ES_{\ell}(n)$ on $\ell$.

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