On the Erdős-Szekeres convex polygon problem

DOI10.1090/JAMS/869MaRDI QIDQ5280069zbMATH OpenOpenAlexWikidataFDO

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

convex \(n\)-gonErdős-Szekeres theoremgeneral position

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(68)

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