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

Ramsey theoryconvex polygonsErdős-Szekeres problem

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

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

• 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?)
• Erdős-Szekeres without induction
• Finding convex sets among points in the plane
• Forced convex \(n\)-gons in the plane
• Note on the Erdős-Szekeres theorem

Cited in

(19)

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

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)