论文标题
带有大色数的HASSE图
Hasse diagrams with large chromatic number
论文作者
论文摘要
对于每个正整数$ n $，我们都会构建一个带有$ n $顶点和色度$ω（n^{1/4}）$的HASSE图，这在先前已知的具有色数$θ（\ log log n）$的载体图的最佳结构上大大改善了。此外，如果我们还要求我们的HASSE图至少具有$ k \ geq 5 $，我们可以实现至少$ n^{\ frac {1} {2k-3} {2k-3}+o（1）} $的色数。 这些结果具有以下令人惊讶的几何后果。它们暗示存在$ n $ curves the Plane的$ \ Mathcal {C} $的存在，以使$ \ Mathcal {C} $的差异图$ g $是无三角形的（或具有高圆形），但是$ g $的色度为$ n $ n $ n $。同样，由于Pach，Tardos和Tóth，先前已知的最佳结构只有对数色数。
For every positive integer $n$, we construct a Hasse diagram with $n$ vertices and chromatic number $Ω(n^{1/4})$, which significantly improves on the previously known best constructions of Hasse diagrams having chromatic number $Θ(\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óth, had only logarithmic chromatic number.
