An improved upper bound for the Erdős-Szekeres conjecture

Let \(ES(n)\) denote the minimum natural number such that every set of \(ES(n)\) points in general position in the plane contains \(n\) points in convex position. In 1935, Erdős and Szekeres proved that \(ES(n) \le {2n-4 \choose n-2}+1\). In 1961, they obtained the lower bound \(2^{n-2}+1 \le ES(n)\...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-05
Main Authors: Mojarrad, Hossein Nassajian, Vlachos, Georgios
Format: Article
Language:English
Subjects:
Lower bounds
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let \(ES(n)\) denote the minimum natural number such that every set of \(ES(n)\) points in general position in the plane contains \(n\) points in convex position. In 1935, Erdős and Szekeres proved that \(ES(n) \le {2n-4 \choose n-2}+1\). In 1961, they obtained the lower bound \(2^{n-2}+1 \le ES(n)\), which they conjectured to be optimal. In this paper, we prove that $$ES(n) \le {2n-5 \choose n-2}-{2n-8 \choose n-3}+2 \approx \frac{7}{16} {2n-4 \choose n-2}.$$
ISSN:2331-8422