Sets in R^ d with no large empty convex subsets

DOI10.1016/0012-365X(92)90665-3MaRDI QIDQ1201240zbMATH OpenOpenAlexFDO

Authors Pavel Valtr

Publication date 17 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90665-3

zbMATH Keywords

convex holeconvex hullfinite sets

Mathematics Subject Classification ID

Designs and configurations (05B99) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Review text

Let \(A\) be a finite set of points in general position in \(\mathbb{R}^ d\), \(d\geq 2\). A subset \(B\subseteq A\) of \(n\) points is called an \(n\)-hole in \(A\) if the points in \(B\) are the vertices of a convex polytope which contains no other point of \(A\). Let \(h(d)\) be the maximum number \(n\) such that any sufficiently large set of points in general position in \(\mathbb{R}^ d\) contains an \(n\)-hole. The author shows that \[ 2d+1\leq h(d)\leq 2^{d-1}(P(d-1)+1), \] where \(P(d-1)\) denotes the product of the smallest \(d-1\) prime numbers. He also gives an improved upper bound in \(\mathbb{R}^ 3\), namely \(h(3)\leq 22\).

Recommendations

• On convex holes in d-dimensional point sets
• A sufficient condition for the existence of large empty convex polygons
• Large convex holes in random point sets
• On empty convex polytopes
• Holes in 2-convex point sets

Cites work

• Convex independent sets and 7-holes in restricted planar point sets
• Konvexe Fünfecke in ebenen Punktmengen
• Sets with No Empty Convex 7-Gons

Cited in

(25)

• Some Erdős-Szekeres type results about points in space
• Subsets of \(\mathbb{R}^ n\) with convex midsets
• On empty convex polytopes
• Chromatic variants of the Erdős--Szekeres theorem on points in convex position.
• Point configurations in \(d\)-space without large subsets in convex position
• Tropical combinatorial Nullstellensatz and sparse polynomials
• A superlinear lower bound on the number of 5-holes
• Large area convex holes in random point sets
• The Erdős-Szekeres Problem
• scientific article; zbMATH DE number 6672582 (Why is no real title available?)
• The Erdos-Szekeres problem on points in convex position – a survey
• Convex polygons in Cartesian products
• The number of holes in the union of translates of a convex set in three dimensions
• On convex holes in d-dimensional point sets
• Holes in 2-convex point sets
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• Ramsey-remainder for convex sets and the Erdős-Szekeres theorem
• Holes and islands in random point sets
• Tight bounds on the expected number of holes in random point sets
• Fixing a hole
• A SAT attack on Erdős-Szekeres numbers in \(\mathbb{R}^d\) and the empty hexagon theorem
• A SAT attack on higher dimensional Erdős-Szekeres numbers
• Erdős-Szekeres-type problems in the real projective plane
• On Erdős-Szekeres Maker-Breaker games
• Convex solid subsets of \(L_{0}(X, \mu)\)

This page was built for publication: Sets in \(\mathbb{R}^ d\) with no large empty convex subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201240)