Hasse diagrams with large chromatic number

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\ge 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óth, had only logarithmic chromatic number.

arXiv comment11 pages, 1 figure