pith. sign in

arxiv: 1505.07549 · v1 · pith:QVUSXCY4new · submitted 2015-05-28 · 🧮 math.CO

On a conjecture of ErdH{o}s and Szekeres

classification 🧮 math.CO
keywords boundchooseupperfracprovedszekerestheybeen
0
0 comments X
read the original abstract

Let f(n) denote the smallest positive integer such that every set of $f(n)$ points in general position in the Euclidean plane contains a convex n-gon. In a seminal paper published in 1935, Erd\H{o}s and Szekeres proved that f(n) exists and provided an upper bound. In 1961, they also proved a lower bound, which they conjectured is optimal. Their bounds are: $2^{n-2}+1 \leq f(n) \leq {2n - 4 \choose n-2}+1$. Since then, the upper bound has been improved by rougly a factor of 2, to $f(n) \leq {2n - 5 \choose n-2}+1$. In the current paper, we further improve the upper bound by proving that: $$ \limsup\limits_{n\rightarrow \infty} \frac{f(n)}{{2n-5 \choose n-2}} \leq \frac{29}{32}$$

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Combinatorial Geometry of Erd\H{o}s--Szekeres Type Problems: SAT/ASP Modeling and Linear Subreduction

    math.CO 2026-04 unverdicted novelty 7.0

    The paper proves h_nc(4,0;4,0)=26 using SAT/ASP solvers and linear subreduction, showing that 26 bicolored points in general position always include an empty monochromatic quadrilateral.