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)≤(2n−4n−2)+1. In 1961, they obtained the lower bound 2n−2+1≤ES(n), which they conjectured to be optimal....
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110213 |
| _version_ | 1826200514091548672 |
|---|---|
| author | Mojarrad, Hossein Nassajian Vlachos, Georgios |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Mojarrad, Hossein Nassajian Vlachos, Georgios |
| author_sort | Mojarrad, Hossein Nassajian |
| collection | MIT |
| description | 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)≤(2n−4n−2)+1. In 1961, they obtained the lower bound 2n−2+1≤ES(n), which they conjectured to be optimal. In this paper, we prove that
ES(n)≤(2n−5n−2)−(2n−8n−3+2)≈716(2n−4n−2). |
| first_indexed | 2024-09-23T11:37:38Z |
| format | Article |
| id | mit-1721.1/110213 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:37:38Z |
| publishDate | 2017 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1102132022-09-27T20:50:37Z An Improved Upper Bound for the Erdős–Szekeres Conjecture Mojarrad, Hossein Nassajian Vlachos, Georgios Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Vlachos, Georgios 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)≤(2n−4n−2)+1. In 1961, they obtained the lower bound 2n−2+1≤ES(n), which they conjectured to be optimal. In this paper, we prove that ES(n)≤(2n−5n−2)−(2n−8n−3+2)≈716(2n−4n−2). Swiss National Science Foundation (Grant 200020-144531) Swiss National Science Foundation (Grant 200021-137574) Swiss National Science Foundation (Grant 200020-162884) 2017-06-23T16:05:16Z 2017-06-23T16:05:16Z 2016-05 2016-04 2016-06-30T12:07:29Z Article http://purl.org/eprint/type/JournalArticle 0179-5376 1432-0444 http://hdl.handle.net/1721.1/110213 Mojarrad, Hossein Nassajian, and Georgios Vlachos. “An Improved Upper Bound for the Erdős–Szekeres Conjecture.” Discrete Comput Geom 56, no. 1 (May 25, 2016): 165–180. en http://dx.doi.org/10.1007/s00454-016-9791-5 Discrete & Computational Geometry Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Science+Business Media New York application/pdf Springer US Springer US |
| spellingShingle | Mojarrad, Hossein Nassajian Vlachos, Georgios An Improved Upper Bound for the Erdős–Szekeres Conjecture |
| title | An Improved Upper Bound for the Erdős–Szekeres Conjecture |
| title_full | An Improved Upper Bound for the Erdős–Szekeres Conjecture |
| title_fullStr | An Improved Upper Bound for the Erdős–Szekeres Conjecture |
| title_full_unstemmed | An Improved Upper Bound for the Erdős–Szekeres Conjecture |
| title_short | An Improved Upper Bound for the Erdős–Szekeres Conjecture |
| title_sort | improved upper bound for the erdos szekeres conjecture |
| url | http://hdl.handle.net/1721.1/110213 |
| work_keys_str_mv | AT mojarradhosseinnassajian animprovedupperboundfortheerdosszekeresconjecture AT vlachosgeorgios animprovedupperboundfortheerdosszekeresconjecture AT mojarradhosseinnassajian improvedupperboundfortheerdosszekeresconjecture AT vlachosgeorgios improvedupperboundfortheerdosszekeresconjecture |