Depth with respect to a family of convex sets. arXiv:1612.03435

Martínez-Sandoval, Leonardo; Tamam, Roee

Preprint, arXiv:1612.03435 [math.CO] (2016).

Summary: We propose a notion of depth with respect to a finite family \(\mathcal{F}\) of convex sets in \(\mathbb{R}^d\) which we call \(\text{dep}_\mathcal{F}\). We begin showing that \(\text{dep}_\mathcal{F}\) satisfies some expected properties for a measure of depth and that this definition is closely related to the notion of depth proposed by J. Tukey. We show that some properties of Tukey depth extend to \(\text{dep}_\mathcal{F}\) and we point out some key differences. We then focus on the following centerpoint-type question: what is the best depth \(\alpha_{d,k}\) that we can guarantee under the hypothesis that the family \(\mathcal{F}\) is \(k\)-intersecting? We show a key connection between this problem and a purely combinatorial problem on hitting sets. The relationship is useful in both directions. On the one hand, for values of \(k\) close to \(d\) the combinatorial interpretation gives a good bound for \(k\). On the other hand, for low values of \(k\) we can use the classic Rado’s centerpoint theorem to get combinatorial results of independent interest. For intermediate values of \(k\) we present a probabilistic framework to improve the bounds and illustrate its use in the case \(k\approx d/2\). These results can be though of as an interpolation between Helly’s theorem and Rado’s centerpoint theorem. As an application of these results we find a Helly-type theorem for fractional hyperplane transversals. We also give an alternative and simpler proof for a transversal result of A. Holmsen.

MSC:

52A35	Helly-type theorems and geometric transversal theory
52A20	Convex sets in \(n\) dimensions (including convex hypersurfaces)