Some Erdős-Szekeres type results about points in space
type: Item
instance of: scholarly article
title: Some Erdős-Szekeres type results about points in space
zbMATH Open document ID: 0811.52005
DOI: 10.1007/BF01305772
author: Valeriu Soltan
author: T. Bisztriczky
published in: Monatshefte für Mathematik
publication date: 1994-10-09T00:00:00Z
full work available at URL: https://eudml.org/doc/178655
review text: Let \(f(n,d)\) and \(g(n,d)\) denote the least integer \(k \geq n\) such that any set of at least \(k\) points in \(E^ d\) contains a subset of \(n\) points which are the vertices of a convex polytope for \(f\), and for \(g\) we demand the additional condition that the polytope be empty (its interior contains no points of the set). Thus \(f(n,d) \leq g(n,d)\). An old result of Erdős and Szekeres (generalized by Grünbaum) states that \(f(n,d)\) is finite for all \(n\) and \(d\). However, \(g(n,d)\) exists only up to \(n = 6\) for \(d = 2\). Its domain of existence is not known for all \(d\); \textit{P. Valtr} [Discrete Math. 108, No. 1-3, 115-124 (1992; Zbl 0766.52003)] proved that it exists for \(n \leq 2d + 1\), and does not for \(n > 2^{d - 1}(N(d - 1) + 1)\), where \(N(d - 1)\) is the product of the smallest \(d - 1\) primes. The authors prove that \(f(n,d)\) is also the smallest \(k \geq n\) such that any set of \(k\) points spanning \(E^ d\) contain \(n\) points on the boundary of the convex hull whose affine hull is also \(E^ d\). They also prove that, for \(d \geq 2\) and \(1 \leq k \leq \lfloor d/2 \rfloor + 1\), we have \(g(d + k,d) \leq d + 2k - 1\). So far, we thus know that \(f(d + 1) = g(d + 1) = d + 1\) (trivial), \(f(n,2) = g(n,2) = d + 3\) (well-known for \(f\), consequence of the above for \(g\)), and that \(g(d + 3, d) \leq d + 5\). For the latter, the following tight results are also proved: \(f(6,3) = g(6,3) = 9\), \(g(7,4) = 9\).
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 650847
zbMATH Keywords: Erdős-Szekeres type results
zbMATH Keywords: points in \(n\)-space
zbMATH Keywords: convex polytopes
zbMATH Keywords: geometric Ramsey theory
MaRDI profile type: Publication
cites work: Q5759552
cites work: Q5511980
cites work: Q5547252
cites work: Konvexe Fünfecke in ebenen Punktmengen
cites work: Sets with No Empty Convex 7-Gons
cites work: Q5628820
cites work: Sets in \(\mathbb{R}^ d\) with no large empty convex subsets
OpenAlex ID: W2065786863
Recommended article: On empty convex polytopes
Recommended article: A result of the existence with three types of interior points
Recommended article: EMPTY CONVEX 5-GONS IN PLANAR POINT SETS
Recommended article: Forced convex \(n\)-gons in the plane
Recommended article: Point configurations in \(d\)-space without large subsets in convex position
Recommended article: Danzer-Grünbaum's theorem revisited
Recommended article: An Erdős-Szekeres type problem in the plane
Recommended article: More on an Erdős-Szekeres-type problem for interior points
Recommended article: Point sets with small integer coordinates and no large convex polygons
Recommended article: On the Erdös-Szekeres problem
description: scientific article; zbMATH DE number 650847