On a conjecture of ErdH{o}s and Szekeres
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.
Forward citations
Cited by 1 Pith paper
-
Combinatorial Geometry of Erd\H{o}s--Szekeres Type Problems: SAT/ASP Modeling and Linear Subreduction
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.