{
  "id": "1703.05253",
  "version": "v1",
  "published": "2017-03-15T16:54:08.000Z",
  "updated": "2017-03-15T16:54:08.000Z",
  "title": "A superlinear lower bound on the number of 5-holes",
  "authors": [
    "Oswin Aichholzer",
    "Martin Balko",
    "Thomas Hackl",
    "Jan Kynčl",
    "Irene Parada",
    "Manfred Scheucher",
    "Pavel Valtr",
    "Birgit Vogtenhuber"
  ],
  "comment": "29 pages, 14 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $P$ be a finite set of points in the plane in general position, that is, no three points of $P$ are on a common line. We say that a set $H$ of five points from $P$ is a $5$-hole in $P$ if $H$ is the vertex set of a convex $5$-gon containing no other points of $P$. For a positive integer $n$, let $h_5(n)$ be the minimum number of 5-holes among all sets of $n$ points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for $h_5(n)$ have been of order $\\Omega(n)$ and $O(n^2)$, respectively. We show that $h_5(n) = \\Omega(n\\log^{4/5}{n})$, obtaining the first superlinear lower bound on $h_5(n)$. The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set $P$ of points in the plane in general position is partitioned by a line $\\ell$ into two subsets, each of size at least 5 and not in convex position, then $\\ell$ intersects the convex hull of some 5-hole in $P$. The proof of this result is computer-assisted.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-03-15T16:54:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52C10",
      "G.2.1"
    ],
    "keywords": [
      "general position",
      "first superlinear lower bound",
      "finite set",
      "convex hull",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}