Abstract | ||
---|---|---|
Let $g(n)$ denote the least integer such that among any $g(n)$ points in general position in the plane there are always $n$ in convex position. In 1935 P. Erd\H os and G. Szekeres showed that $g(n)$ exists and $2^{n-2}+1\le g(n)\le {2n-4\choose n-2}+1$. Recently, the upper bound has been slightly improved by Chung and Graham and by Kleitman and Pachter. In this note we further improve the upper bound to $$g(n)\le {2n-5\choose n-2}+2.$$ |
Year | DOI | Venue |
---|---|---|
1998 | 10.1007/PL00009363 | Discrete & Computational Geometry |
Keywords | Field | DocType |
convex position,h os,g. szekeres,general position,erdos-szekeres theorem,p. erd,upper bound | Integer,General position,Combinatorics,Upper and lower bounds,Convex position,Mathematics | Journal |
Volume | Issue | ISSN |
19 | 3 | 0179-5376 |
Citations | PageRank | References |
14 | 1.38 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Géza Tóth | 1 | 72 | 9.25 |
Pavel Valtr | 2 | 397 | 77.30 |