{
  "id": "1710.11415",
  "version": "v1",
  "published": "2017-10-31T11:42:48.000Z",
  "updated": "2017-10-31T11:42:48.000Z",
  "title": "Two extensions of the Erős--Szekeres problem",
  "authors": [
    "Andreas F. Holmsen",
    "Hossein Nassajian Mojarrad",
    "János Pach",
    "Gábor Tardos"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "According to Suk's breakthrough result on the Erd\\H{o}s--Szekeres problem, any point set in general position in the plane, which has no $n$ elements that form the vertex set of a convex $n$-gon, has at most $2^{n+O\\left({n^{2/3}\\log n}\\right)}$ points. We strengthen this theorem in two ways. First, we show that the result generalizes to convexity structures induced by pseudoline arrangements. Second, we improve the error term. A family of $n$ convex bodies in the plane is said to be in convex position if the convex hull of the union of no $n-1$ of its members contains the remaining one. If any three members are in convex position, we say that the family is in {\\em general position}. Combining our results with a theorem of Dobbins, Holmsen, and Hubard, we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes T\\'{o}th and by Pach and T\\'{o}th, respectively. Let $c(n)$ (and $c'(n)$) denote the smallest positive integer $N$ with the property that any family of $N$ pairwise disjoint convex bodies in general position (resp., $N$ convex bodies in general position, any pair of which share at most two boundary points) has an $n$-membered subfamily in convex position. We show that $c(n)\\le c'(n)\\leq 2^{n+O\\left(\\sqrt{n\\log n}\\right)}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-10-31T11:42:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "general position",
      "erős-szekeres problem",
      "convex position",
      "extensions",
      "pairwise disjoint convex bodies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}