← All problems

Erdős Problem #651 — Subexponential higher-dimensional Erdős–Szekeres numbers

29 years old · traced to

For integers d≥3d\geq 3 and n≥3n\geq 3, a finite set X⊂RdX\subset\mathbb{R}^d is in general position if no d+1d+1 of its points lie in one affine hyperplane. A subset is in convex position if all its points are vertices of its convex hull. Let ESd(n)ES_d(n) be the least integer NN such that every set of NN points in general position in Rd\mathbb{R}^d contains an nn-point subset in convex position. The question is whether, for each fixed d≥3d\geq 3, there is a constant cd>0c_d>0 such that

ESd(n)≥(1+cd)nES_d(n)\geq (1+c_d)^n

for all sufficiently large nn. Pohoata and Zakharov (2022)

Background

Erdős and Szekeres introduced the planar problem in 1935, proving that a finite threshold exists; in 1960 they established the lower bound ES2(n)≥2n−2+1ES_2(n)\geq 2^{n-2}+1 and conjectured that their construction was optimal. In higher dimensions the threshold also exists, by a Ramsey-theoretic argument, but that gives comparatively weak quantitative bounds. Whether the three-dimensional numbers might be substantially smaller than the planar ones had been debated, with conflicting predictions. Morris and Soltan conjectured an exponential-scale lower bound in every dimension, a prediction contradicted by the result below. Pohoata and Zakharov (2022)

References

C. Pohoata and D. Zakharov, Convex polytopes from fewer points, arXiv:2208.04878 (2022).

Source: C. Pohoata and D. Zakharov, Convex polytopes from fewer points, arXiv:2208.04878 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.