On the Erdős-Szekeres convex polygon problem

DOI10.1090/JAMS/869MaRDI QIDQ5280069zbMATHOpenAlexWikidataFDO

Authors Andrew Suk

Publication date 20 July 2017

Published in Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.08657

zbMATH Keywords

general positionconvex \(n\)-gonErdős-Szekeres theorem

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Ramsey theory (05D10)

Abstract: Let $ES(n)$ be the smallest integer such that any set of $ES(n)$ points in the plane in general position contains $n$ points in convex position. In their seminal 1935 paper, Erdos and Szekeres showed that $ES(n)leq2n-4choosen-2+1=4^{n-o(n)}$. In 1960, they showed that $ES(n)geq{2}^{n-2}+1$ and conjectured this to be optimal. In this paper, we nearly settle the Erdos-Szekeres conjecture by showing that $ES(n)=2^{n+o(n)}$.

Recommendations

• An improved upper bound for the Erdős-Szekeres conjecture
• Erdős-Szekeres without induction
• scientific article; zbMATH DE number 1786502
• scientific article; zbMATH DE number 5019923
• Two upper bounds for the Erdős-Szekeres number with conditions

Cites work

• scientific article; zbMATH DE number 981684 (Why is no real title available?)
• scientific article; zbMATH DE number 3168302 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 5019923 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• A note on order-type homogeneous point sets
• A positive fraction Erdős-Szekeres theorem
• An improved upper bound for the Erdős-Szekeres conjecture
• Canonical theorems for convex sets
• Erdős-Szekeres without induction
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Finding convex sets among points in the plane
• Forced convex \(n\)-gons in the plane
• Note on the Erdős-Szekeres theorem
• Order types of convex bodies
• Point configurations in \(d\)-space without large subsets in convex position
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• Ramsey-remainder for convex sets and the Erdős-Szekeres theorem
• Research Problems in Discrete Geometry
• The Erdos-Szekeres problem on points in convex position – a survey
• The Erdős-Szekeres problem for non-crossing convex sets
• The partitioned version of the Erdős-Szekeres theorem

Cited in

(50)

• Two extensions of the Erdős-Szekeres problem
• On some extremal results for order types
• On disjoint holes in point sets
• The Dirac-Goodman-Pollack conjecture
• An improved upper bound for the Erdős-Szekeres conjecture
• On the Erdős-Szekeres \(n\)-interior-point problem
• A generalization of the Erdös-Szekeres convex n-gon theorem.
• On a problem of Erdős and Rothschild on edges in triangles
• Unavoidable patterns in complete simple topological graphs
• Two disjoint 5-holes in point sets
• The parameterized complexity of finding point sets with hereditary properties
• A new proof of the Erdős-Szekeres convex k-gon result
• Erdős-Szekeres theorem for \(k\)-flats
• On the Erdős-Tuza-Valtr conjecture
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• Saturation problems in the Ramsey theory of graphs, posets and point sets
• Tverberg-type theorems with altered intersection patterns (nerves)
• A partial proof of the Erdős-Szekeres conjecture for hexagons
• Erdős--Szekeres theorem with forbidden order types
• Unavoidable patterns in complete simple topological graphs
• A breakthrough in the Erdős-Szekeres problem
• Erdős-Szekeres ``happy end-type theorems for separoïds
• A SAT attack on higher dimensional Erdős-Szekeres numbers
• Point sets with small integer coordinates and no large convex polygons
• On the Erdös-Szekeres problem
• A simple proof for open cups and caps
• The Erdős-Szekeres problem and an induced Ramsey question
• Faster counting empty convex polygons in a planar point set
• Fast formal proof of the Erdős-Szekeres conjecture for convex polygons with at most 6 points
• A Semiring on Convex Polygons and Zero-Sum Cycle Problems
• The Erdős-Szekeres problem for non-crossing convex sets
• A SAT attack on the Erdős-Szekeres conjecture
• Computer solution to the 17-point Erdős-Szekeres problem
• On the number of points in general position in the plane
• The never-ending happiness of Paul Erdős's mathematics
• Erdős-Szekeres-type problems in the real projective plane
• A SAT attack on the Erdős-Szekeres conjecture
• scientific article; zbMATH DE number 1940907 (Why is no real title available?)
• Convex drawings of the complete graph: topology meets geometry
• A SAT attack on Erdős-Szekeres numbers in \(\mathbb{R}^d\) and the empty hexagon theorem
• Convex hulls of random order types
• scientific article; zbMATH DE number 468661 (Why is no real title available?)
• scientific article; zbMATH DE number 1786502 (Why is no real title available?)
• The Erdos-Szekeres problem on points in convex position – a survey
• New bounds for the same-type lemma
• Convex polygons in Cartesian products
• On the computational complexity of Erdős-Szekeres and related problems in \(\mathbb{R}^{3}\)
• Twenty years of progress of \(\mathrm{JCDCG}^3\)
• A construction for Boolean cube Ramsey numbers
• On weighted sums of numbers of convex polygons in point sets

This page was built for publication: On the Erdős-Szekeres convex polygon problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280069)