2015/10/21 by Hossein Nassajian Mojarrad, Mojarrad, Hossein Nassajian, Georgios Vlachos +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Search Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1510.06255
openalex publication_date 2015/10/21 · openalex created_date 2017/06/30 · openalex updated_date 2026/07/28
Let ES(n) denote the minimum natural number such that every set of ES(n)\npoints in general position in the plane contains n points in convex position.\nIn 1935, Erd Hos and Szekeres proved that ES(n) \≤ 2n-4 choose n-2+1.\nIn 1961, they obtained the lower bound 2n-2+1 \≤ ES(n), which they\nconjectured to be optimal. In this paper, we prove that ES(n)
le 2n-5\n
choose n-2-2n-8
choose n-3+2
approx
frac716 2n-4
choose n-2.\n