{
  "id": "1612.03435",
  "version": "v1",
  "published": "2016-12-11T16:55:30.000Z",
  "updated": "2016-12-11T16:55:30.000Z",
  "title": "Depth with respect to a family of convex sets",
  "authors": [
    "Leonardo Martínez-Sandoval",
    "Roee Tamam"
  ],
  "comment": "14 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-12-11T16:55:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52A35",
      "52A20"
    ],
    "keywords": [
      "convex sets",
      "classic rados centerpoint theorem",
      "tukey depth extend",
      "fractional hyperplane transversals",
      "purely combinatorial problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}