论文标题
通过磁盘实现M-均匀的四色超图
Realizing an m-uniform four-chromatic hypergraph with disks
论文作者
论文摘要
我们证明，对于每一个$ m $，都有一个有限的点集$ \ MATHCAL {p} $在飞机上，以至于无论$ \ Mathcal {p} $是三色的，总有一个圆盘，完全包含$ m $点，所有同一颜色。这改善了Pach，Tardos和Tóth的结果，他们对两种颜色证明了这一点。结构的主要成分是一个子构建，其点位于凸位。也就是说，我们表明，对于每$ m $，都有一个有限点集合$ \ mathcal {p} $在凸位置的飞机上，以便无论$ \ nathcal {p} $是两色的，总有一个完全包含$ m $点的磁盘，所有相同的颜色。我们还证明，对于单元磁盘，没有类似的结构可以起作用，还有其他几个结果。
We prove that for every $m$ there is a finite point set $\mathcal{P}$ in the plane such that no matter how $\mathcal{P}$ is three-colored, there is always a disk containing exactly $m$ points, all of the same color. This improves a result of Pach, Tardos and Tóth who proved the same for two colors. The main ingredient of the construction is a subconstruction whose points are in convex position. Namely, we show that for every $m$ there is a finite point set $\mathcal{P}$ in the plane in convex position such that no matter how $\mathcal{P}$ is two-colored, there is always a disk containing exactly $m$ points, all of the same color. We also prove that for unit disks no similar construction can work, and several other results.
