Fixing a hole

. The key step in our proof, which may be of independent interest, is to show that there are arbitrarily small perturbations of the set of lattice points

[n]^{d}

with no large holes.

Review text

A set \(S\subset\mathbb{R}^d\) is in \textit{general position} if for every \(k<d\) and every affine \(k\)-dimensional subspace \(V\), \(\lvert S\cap V\rvert\leq k+1\). The famous ``happy ending problem states that for any set of five points in general position, there exists a subset of four points that form the vertices of a convex quadrilateral. Erdős and Szekeres generalised this in [\textit{P. Erdős} and \textit{G. Szekeres}, Compos. Math. 2, 463--470 (1935; Zbl 0012.27010)] to say that for any integer \(\ell\) there exists an integer \(n\geq\ell\) such that any set \(S\) of \(n\) points in general position contains a subset of \(\ell\) points that form the vertices of a convex \(\ell\)-gon. The analogue of this statement in higher dimensions follows as a corollary. A variant of this problem, later introduced by \textit{P. Erdős} [Aust. Math. Soc. Gaz. 5, 52--54 (1978; Zbl 0417.52002); Colloq. Math. Soc. Janos Bolyai 25, 137--148 (1981; Zbl 0472.10001)], asks if the statement remains true if we further require the convex polytope with \(\ell\) vertices not to include any point of \(S\) in its interior. In other words, if the polytope is an \textit{\(\ell\)-hole}. In the plane, this was disproven by \textit{J. D. Horton} [Can. Math. Bull. 26, 482--484 (1983; Zbl 0521.52010)] for \(\ell\geq 7\) using a construction which has come to be referred to as \textit{Horton sets}. In higher dimensions, \textit{P. Valtr} [Discrete Math. 108, No. 1--3, 115--124 (1992; Zbl 0766.52003)] used Horton-type sets to find an upper bound for \(\ell\) which depends on the dimension. The present paper builds on these ideas. The question the authors ask concerns sets in general position with large holes. Given such a set, is it always possible to find supersets in general position with no large holes? In Theorem 1.1 the authors answer their question in the affirmative: For every dimension \(d\), they give an integer \(C_d = d^{O(d^3)}\) such that any set in general position can be extended to a set in general position with no \(C_d\)-holes. The authors prove this theorem using Theorem 1.2 which states that in any dimension \(d\geq 2\), and for any \(n\geq 1\) and any \(\varepsilon>0\), there exists an integer \(C_d^\prime=d^{O(d^3)}\) and a map \(f\colon [n]^d\to\mathbb{R}^d\) with \(\|x-f(x)\| <\varepsilon\) for all \(x\in [n]^d\) such that \(f([n]^d)\) has no \(C_d^\prime\)-holes. The paper consists of a total of four sections. The proof of the second theorem splits into two parts, the planar case which is treated in Section 2, and the non-planar case in Section 3. This structuring is motivated by the fact that the planar case is already implicity treated in [\textit{P. Valtr}, Discrete Comput. Geom. 7, No. 2, 135--152 (1992; Zbl 0748.52005)]. However, as a side effect, it leads to a nice flow of the paper where the Section 2 helps the reader build intuition and Section 3 emerges as a natural extension. The last section includes a corollary of the second theorem about the \textit{spread} of a set \(S\), which is defined as the maximum distance between any pair of points divided by the minimum distance of any pair of points in \(S\).

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Fixing a hole

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