2015/05/28 by Georgios Vlachos, Vlachos, Georgios
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Packing Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1505.07549
openalex publication_date 2015/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let f(n) denote the smallest positive integer such that every set of f(n)\npoints in general position in the Euclidean plane contains a convex n-gon. In a\nseminal paper published in 1935, Erd Hos and Szekeres proved that f(n) exists\nand provided an upper bound. In 1961, they also proved a lower bound, which\nthey conjectured is optimal. Their bounds are: 2n-2+1 \≤ f(n) \≤ 2n -\n4 choose n-2+1. Since then, the upper bound has been improved by rougly a\nfactor of 2, to f(n) \≤ 2n - 5 choose n-2+1. In the current paper, we\nfurther improve the upper bound by proving that: \n
limsup
limitsn
rightarrow
infty
fracf(n)2n-5
choose n-2
leq\n
frac2932\n