Around Erdős-Szekeres problems
type: Item
instance of: scholarly article
title: Around Erdős-Szekeres problems
zbMATH Open document ID: 1181.52027
DOI: 10.1134/S1064562409030168
author: V. A. Koshelev
published in: Doklady Mathematics
publication date: 2009-10-26T00:00:00Z
review text: A classic theorem of Erdős and Szekeres asserts that for every \(n\geq 3\), there exists a smallest number \(g(n)\) such that any \(g(n)\) points in the plane in general position (i.e., no 3 collinear) contain the vertices of a convex \(n\)-gon. \textit{A. Bialostocki, P. Dieker} and \textit{B. Voxman} [Discrete Math. 91, 231--238 (1991; Zbl 0769.52014)] suggested the following variant of the Erdős-Szekeres problem: Given arbitrary integer \(n\geq 4\) and \(q\geq 2\), find the smallest positive integer \(h(n, \text{mod} q)\), such that any planar point set \(H\) in general position, of at least \(h(n, \text{mod} q)\) points, contains a subset of cardinality \(n\), whose elements are the vertices of a convex \(n\)-gon \(C\), such that the number of points of \(H\) in the interior of \(C\) is a multiple of \(q\). The paper proves the following new results: (1) If \(n\geq 2q-1\), then \(h(n,\text{mod} q) \leq g(4+(n-4)q)\); (2) If \(n\geq q+2\) and \(q\) is even, then \(h(n,\text{mod} q) \leq R_q^3(n,n,\dots ,n)\); (3) If \(n\geq q+2\) and \(q\) is odd, then \(h(n,\text{mod} q) \leq R_q^3(g(n),n,n,\dots ,n)\). (\(R_k^p\) refers to Ramsey numbers for \(k\)-coloring \(p\)-tuples.)
reviewed by: László A. Székely
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 52A37
zbMATH DE Number: 5621458
zbMATH Keywords: Erdős-Szekeres problem
MaRDI profile type: Publication
cites work: The Erdos-Szekeres problem on points in convex position – a survey
cites work: Some notes on the Erdős-Szekeres theorem
cites work: Computer solution to the 17-point Erdős-Szekeres problem
cites work: On the Erdös-Szekeres problem
cites work: Sets with No Empty Convex 7-Gons
cites work: On the generalized Erdös-Szekeres conjecture -- a new upper bound
Recommended article: A minimal planar point set containing a disjoint pair of a convex 4-gon and a convex 6-gon
Recommended article: Interior points in the Erdős-Szekeres theorems
Recommended article: Q4547794
Recommended article: A Remark on the Erdos-Szekeres Theorem
Recommended article: An Erdős-Szekeres type problem in the plane
Recommended article: On the Erdös-Szekeres problem
Recommended article: The Erdos-Szekeres problem on points in convex position – a survey
Recommended article: The Erdős-Szekeres theorem and congruences
Recommended article: Forced convex \(n\)-gons in the plane
Recommended article: More on an Erdős-Szekeres-type problem for interior points
description: scientific article; zbMATH DE number 5621458