An improved upper bound for the Erdős-Szekeres conjecture

DOI10.1007/S00454-016-9791-5MaRDI QIDQ306509zbMATH OpenOpenAlexWikidataFDO

Authors Hossein Nassajian Mojarrad, Georgios Vlachos

Publication date 31 August 2016

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

convex polygonsErdős-Szekeres problemRamsey theory

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Abstract: 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, ErdH{o}s and Szekeres proved that $ES(n)le2n-4choosen-2+1$. In 1961, they obtained the lower bound $2^{n-2}+1leES(n)$, which they conjectured to be optimal. In this paper, we prove that ${\displaystyle }$ES(n) le {2n-5 choose n-2}-{2n-8 choose n-3}+2 approx frac{7}{16} {2n-4 choose n-2}.${\displaystyle }$

Review text

Let \(\mathrm{ES}(n)\) denote the least natural number, such that every set of \(\mathrm{ES}(n)\) points in general position in the plane contains \(n\) points in convex position. \textit{P. Erdős} and \textit{G. Szekeres} [Compos. Math. 2, 463--470 (1935; Zbl 0012.27010); Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 3--4, 53--62 (1961; Zbl 0103.15502)] proved \(2^{n-2} +1 \leq\mathrm{ES}(n)\leq {2n-4\choose n-2}+1\) and conjectured that the lower bound is tight. The paper under review proves the best current upper bound, \(\mathrm{ES}(n)\leq {2n-5\choose n-2} -{2n-8\choose n-3}+2\), which in turn gives \(\limsup_{n\rightarrow \infty} \frac{\mathrm{ES}(n)}{{2n-4\choose n-2}} \leq 7/16\). \textit{S. Norin} and \textit{Y. Yuditsky} [Discrete Comput. Geom. 55, No. 4, 963--971 (2016; Zbl 1351.52018)] reached the same asymptotic upper bound, with a slightly weaker bound.

Recommendations

• scientific article; zbMATH DE number 5019923
• Erdős-Szekeres without induction
• On the Erdős-Szekeres convex polygon problem
• Two upper bounds for the Erdős-Szekeres number with conditions
• On the Erdös-Szekeres problem

Cites work

• Erdős-Szekeres without induction
• Finding convex sets among points in the plane
• Forced convex n-gons in the plane
• scientific article; zbMATH DE number 3168302 (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

Cited in

(23)

• On the generalized Erdös-Szekeres conjecture -- a new upper bound
• Note on the Erdős-Szekeres theorem
• An improved upper bound for Leo Moser's worm problem
• Point sets with small integer coordinates and no large convex polygons
• The Erdős-Szekeres theorem and congruences
• Two extensions of the Erdős-Szekeres problem
• A partial proof of the Erdős-Szekeres conjecture for hexagons
• Improved bounds for Erdős' matching conjecture
• scientific article; zbMATH DE number 979968 (Why is no real title available?)
• scientific article; zbMATH DE number 1498813 (Why is no real title available?)
• scientific article; zbMATH DE number 6169011 (Why is no real title available?)
• A new exponential upper bound for the Erd\H{o}s-Ginzburg-Ziv constant
• On the Erdős-Szekeres convex polygon problem
• scientific article; zbMATH DE number 5019923 (Why is no real title available?)
• A SAT attack on the Erdős-Szekeres conjecture
• An upper bound on the mean value of the Erdős–Hooley Delta function
• An improved bound for the Manickam-Miklós-Singhi conjecture
• Exponential Erdős-Szekeres theorem for matrices
• On the Erdős-Tuza-Valtr conjecture
• Convex polytopes from fewer points
• The Erdős-Szekeres conjecture revisited
• The Erdős-Szekeres conjecture revisited
• New upper bounds for the Davenport and for the Erdős-Ginzburg-Ziv constants

This page was built for publication: An improved upper bound for the Erdős-Szekeres conjecture

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