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

DOI10.1007/S00454-016-9791-5zbMATH Open1351.52017arXiv1510.06255OpenAlexW2239826551WikidataQ123241793 ScholiaQ123241793MaRDI QIDQ306509FDOQ306509

Authors: Hossein Nassajian Mojarrad, Georgios Vlachos 

Publication date: 31 August 2016

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

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

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

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

zbMATH Keywords

Ramsey theoryconvex polygonsErdős-Szekeres problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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
• Erdős-Szekeres without induction

Cited In (17)

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

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)