Skip to content

Erdős problem 107

Let f(n)f(n) be minimal such that any f(n)f(n) points in R2ℝ^2, no three on a line, contain nn points which form the vertices of a convex nn-gon. Prove that f(n)=2n−2+1f(n) = 2^{n-2} + 1.

Sources

The source's own material, retained exactly.

7 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

107.lean

Retained formal statement6 of 7

The current best bound is due to Holmsen, Mojarrad, Pach, and Tardos [HMPT20], who prove f(n)≤2n+O(nlog⁡n). f(n) ≤ 2^{n+O(\sqrt{n\log n})}.

[HMPT20] Holmsen, Andreas F. and Mojarrad, Hossein Nassajian and Pach, János and Tardos, Gábor, _Two extensions of the Erdős-Szekeres problem_. J. Eur. Math. Soc. (JEMS) (2020), 3981-3995.

FormalConjectures/ErdosProblems/107.leanErdos107.variants.hmpt_bound1 lineExact file
∃ r, (r =O[Filter.atTop] fun n => √(↑n * Real.log ↑n)) ∧ ∀ n ≥ 3, ↑(Erdos107.f n) ≤ 2 ^ (↑n + r n)
SolvedStatement only, no proof