On the Erdős-Szekeres convex polygon problem

DOI10.1090/JAMS/869zbMATH Open1370.52032arXiv1604.08657OpenAlexW2964204159WikidataQ55969517 ScholiaQ55969517MaRDI QIDQ5280069FDOQ5280069

Authors: Andrew Suk 

Publication date: 20 July 2017

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

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)}$.

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

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

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)

Cites Work

• Research Problems in Discrete Geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• A decomposition theorem for partially ordered sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Forced convex \(n\)-gons in the plane
• Finding convex sets among points in the plane
• Note on the Erdős-Szekeres theorem
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• An improved upper bound for the Erdős-Szekeres conjecture
• Erdős-Szekeres without induction
• The Erdos-Szekeres problem on points in convex position – a survey
• A NOTE ON ORDER‐TYPE HOMOGENEOUS POINT SETS
• Point configurations in \(d\)-space without large subsets in convex position
• A positive fraction Erdős-Szekeres theorem
• The partitioned version of the Erdős-Szekeres theorem
• Ramsey-remainder for convex sets and the Erdős-Szekeres theorem
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Order types of convex bodies
• Canonical theorems for convex sets
• Title not available (Why is that?)
• The Erdős-Szekeres problem for non-crossing convex sets

Cited In (45)

• Computer solution to the 17-point Erdős-Szekeres problem
• A SAT attack on the Erdős-Szekeres conjecture
• Two disjoint 5-holes in point sets
• Fast formal proof of the Erdős-Szekeres conjecture for convex polygons with at most 6 points
• Convex hulls of random order types
• Title not available (Why is that?)
• New bounds for the same-type lemma
• A partial proof of the Erdős-Szekeres conjecture for hexagons
• Title not available (Why is that?)
• The Erdos-Szekeres problem on points in convex position – a survey
• Erdős-Szekeres theorem for \(k\)-flats
• A simple proof for open cups and caps
• Saturation problems in the Ramsey theory of graphs, posets and point sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• A SAT attack on higher dimensional Erdős-Szekeres numbers
• A Semiring on Convex Polygons and Zero-Sum Cycle Problems
• Twenty years of progress of \(\mathrm{JCDCG}^3\)
• THE ERDŐS–SZEKERES PROBLEM AND AN INDUCED RAMSEY QUESTION
• On the Erdős-Szekeres \(n\)-interior-point problem
• Faster counting empty convex polygons in a planar point set
• A construction for Boolean cube Ramsey numbers
• On some extremal results for order types
• On disjoint holes in point sets
• The Dirac-Goodman-Pollack conjecture
• Tverberg-type theorems with altered intersection patterns (nerves)
• On the Erdös-Szekeres problem
• On the computational complexity of Erdős-Szekeres and related problems in \(\mathbb{R}^{3}\)
• On weighted sums of numbers of convex polygons in point sets
• A generalization of the Erdös-Szekeres convex n-gon theorem.
• A new proof of the Erdős-Szekeres convex k-gon result
• Erdős--Szekeres theorem with forbidden order types
• The Parameterized Complexity of Finding Point Sets with Hereditary Properties
• The never-ending happiness of Paul Erdős's mathematics
• Erdős-Szekeres-type problems in the real projective plane
• Unavoidable patterns in complete simple topological graphs
• Point sets with small integer coordinates and no large convex polygons
• On the Erdős-Tuza-Valtr conjecture
• Erdős-Szekeres ``happy end-type theorems for separoïds
• Convex polygons in Cartesian products
• On a problem of Erdős and Rothschild on edges in triangles
• Unavoidable patterns in complete simple topological graphs
• The Erdős-Szekeres problem for non-crossing convex sets
• Convex drawings of the complete graph: topology meets geometry
• On Erdős-Szekeres-type problems for \(k\)-convex 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)