{
  "id": "1908.05550",
  "version": "v1",
  "published": "2019-08-15T14:02:54.000Z",
  "updated": "2019-08-15T14:02:54.000Z",
  "title": "A sharp threshold phenomenon in string graphs",
  "authors": [
    "Istvan Tomon"
  ],
  "comment": "21 pages, 6 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove that for every $\\epsilon>0$ there exists $\\delta>0$ such that the following holds. Let $\\mathcal{C}$ be a collection of $n$ curves in the plane such that there are at most $(\\frac{1}{4}-\\epsilon)\\frac{n^{2}}{2}$ pairs of curves $\\{\\alpha,\\beta\\}$ in $\\mathcal{C}$ having a nonempty intersection. Then $\\mathcal{C}$ contains two disjoint subsets $\\mathcal{A}$ and $\\mathcal{B}$ such that $|\\mathcal{A}|=|\\mathcal{B}|\\geq \\delta n$, and every $\\alpha\\in \\mathcal{A}$ is disjoint from every $\\beta\\in\\mathcal{B}$. On the other hand, for every positive integer $n$ there exists a collection $\\mathcal{C}$ of $n$ curves in the plane such that there at most $(\\frac{1}{4}+\\epsilon)\\frac{n^{2}}{2}$ pairs of curves $\\{\\alpha,\\beta\\}$ having a nonempty intersection, but if $\\mathcal{A},\\mathcal{B}\\subset \\mathcal{C}$ are such that $|\\mathcal{A}|=|\\mathcal{B}|$ and $\\alpha\\cap \\beta=\\emptyset$ for every $(\\alpha,\\beta)\\in \\mathcal{A}\\times\\mathcal{B}$, then $|\\mathcal{A}|=|\\mathcal{B}|=O(\\frac{1}{\\epsilon}\\log n)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-08-15T14:02:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "sharp threshold phenomenon",
      "string graphs",
      "nonempty intersection",
      "collection",
      "disjoint subsets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}