{
  "id": "2001.09901",
  "version": "v1",
  "published": "2020-01-27T16:38:22.000Z",
  "updated": "2020-01-27T16:38:22.000Z",
  "title": "Hasse diagrams with large chromatic number",
  "authors": [
    "Andrew Suk",
    "István Tomon"
  ],
  "comment": "11 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "For every positive integer $n$, we construct a Hasse diagram with $n$ vertices and chromatic number $\\Omega(n^{1/4})$, which significantly improves on the previously known best constructions of Hasse diagrams having chromatic number $\\Theta(\\log n)$. In addition, if we also require that our Hasse diagram has girth at least $k\\geq 5$, we can achieve a chromatic number of at least $n^{\\frac{1}{2k-3}+o(1)}$. These results have the following surprising geometric consequence. They imply the existence of a family $\\mathcal{C}$ of $n$ curves in the plane such that the disjointness graph $G$ of $\\mathcal{C}$ is triangle-free (or have high girth), but the chromatic number of $G$ is polynomial in $n$. Again, the previously known best construction, due to Pach, Tardos and T\\'oth, had only logarithmic chromatic number.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-01-27T16:38:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hasse diagram",
      "large chromatic number",
      "best construction",
      "logarithmic chromatic number",
      "surprising geometric consequence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}