Two upper bounds for the Erdős-Szekeres number with conditions
type: Item
instance of: scholarly article
title: Two upper bounds for the Erdős-Szekeres number with conditions
zbMATH Open document ID: 1268.52013
author: Florian Strunk
published in: Discrete \& Computational Geometry
publication date: 2013-03-20T00:00:00Z
review text: The celebrated Erdős-Szekeres theorem asserts that there is a smallest positive integer \(ES(n)\), such that among any \(ES(n)\) points in general position in the plane, one finds the vertices of a convex \(n\)-gon, and the Erdős-Szekeres conjecture is that \(ES(n)=2^{n-2}+1\). Erdős and Szekeres proved \(ES(n)\leq \binom{2n-4}{n-2}+1\). The current best upper bound, \(ES(n)\leq \binom{2n-5}{n-2}+1\), is due to \textit{G. Tóth} and \textit{P. Valtr} [Mathematical Sciences Research Institute Publications 52, 557--568 (2005; Zbl 1090.52014)]. The paper under review uses the projective transformation method of Tóth and Valtr to prove the following results: For every \(n\geq 4\), every set of \(\binom{2n-5}{n-2}-2n+9\) points in general position in the plane with the property that there is no point inside a triangle determined by three consecutive vertices of its convex hull contains a convex \(n\)-gon. For every \(n\geq 4\), every set of \(\binom{2n-5}{n-2}-2n+10\) points in general position in the plane, whose convex hull is an \(n-1\)-gon, contains a convex \(n\)-gon.
Mathematics Subject Classification ID: 52C10
zbMATH DE Number: 6147354
zbMATH Keywords: Erdős-Szekeres problem
zbMATH Keywords: discrete geometry
zbMATH Keywords: combinatorial convexity
reviewed by: László A. Székely
MaRDI profile type: Publication
full work available at URL: s00454-012-9474-9
OpenAlex ID: W2116748315
cites work: Forced convex \(n\)-gons in the plane
cites work: Q3286826
cites work: Finding convex sets among points in the plane
cites work: The Erdos-Szekeres problem on points in convex position – a survey
cites work: Computer solution to the 17-point Erdős-Szekeres problem
cites work: Note on the Erdős-Szekeres theorem
cites work: Q5290279
DOI: 10.1007/S00454-012-9474-9
Recommended article: Note on the Erdős-Szekeres theorem
Recommended article: Forced convex \(n\)-gons in the plane
Recommended article: A Remark on the Erdos-Szekeres Theorem
Recommended article: The Erdos-Szekeres problem on points in convex position – a survey
Recommended article: On the Erdös-Szekeres problem
Recommended article: Q4849067
Recommended article: Q5290279
Recommended article: A minimal planar point set containing a disjoint pair of a convex 4-gon and a convex 6-gon
Recommended article: A generalisation of the Erdős-Szekeres theorem to disjoint convex sets
Recommended article: On the minimum size of a point set containing a 5-hole and a disjoint 4-hole
description: scientific article; zbMATH DE number 6147354