{
  "id": "2009.04380",
  "version": "v1",
  "published": "2020-09-09T15:58:37.000Z",
  "updated": "2020-09-09T15:58:37.000Z",
  "title": "Turán-type results for intersection graphs of boxes",
  "authors": [
    "István Tomon",
    "Dmitriy Zakharov"
  ],
  "comment": "4 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this short note, we prove the following analog of the K\\H{o}v\\'ari-S\\'os-Tur\\'an theorem for intersection graphs of boxes. If $G$ is the intersection graph of $n$ axis-parallel boxes in $\\mathbb{R}^{d}$ such that $G$ contains no copy of $K_{t,t}$, then $G$ has at most $ctn(\\log n)^{2d+3}$ edges, where $c=c(d)>0$ only depends on $d$. Our proof is based on exploring connections between boxicity, separation dimension and poset dimension. Using this approach, we also show that a construction of Basit et al. of $K_{2,2}$-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon et al. We show that there exist graphs of separation dimension 4 having superlinear number of edges.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-09T15:58:37.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "intersection graph",
      "turán-type results",
      "separation dimension",
      "free incidence graphs",
      "superlinear number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}