Erdős problem 107 · problems.science

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

Sources

Browse retained paths and inspect the exact material available for this Problem.

7 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

107.lean

Retained formal statement5 of 7

Erdős and Szekeres proved the bounds $2^{n-2} + 1 ≤ f(n) ≤ \binom{2n-4}{n-2} + 1$ ([ErSz60] and [ErSz35] respectively).

[ErSz60] Erdős, P. and Szekeres, G., _On some extremum problems in elementary geometry_. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. (1960/61), 53-62.

[ErSz35] Erdős, P. and Szekeres, G., _A combinatorial problem in geometry_. Compos. Math. (1935), 463-470.

FormalConjectures/ErdosProblems/107.leanErdos107.variants.ersz_bounds1 lineExact file

1∀ n ≥ 3, 2 ^ (n - 2) + 1 ≤ Erdos107.f n ∧ Erdos107.f n ≤ (2 * n - 4).choose (n - 2) + 1

SolvedStatement only, no proof

Sources

Search problems.science