The \emph{chromatic number} of a hypergraph is the smallest number of colors needed to color the vertices such that no edge of at least two vertices is monochromatic. Given a family of geometric objects $\mathcal{F}$ that covers a subset $S$ of the Euclidean space, we can associate it with a hypergraph whose vertex set is $\mathcal F$ and whose edges are those subsets ${\mathcal{F}'}\subset \mathcal F$ for which there exists a point $p\in S$ such that ${\mathcal F}'$ consists of precisely those elements of $\mathcal{F}$ that contain $p$. The question whether $\mathcal F$ can be split into 2 coverings is equivalent to asking whether the chromatic number of the hypergraph is equal to 2. There are a number of competing notions of the chromatic number that lead to deep combinatorial questions already for abstract hypergraphs. In this paper, we concentrate on \emph{geometrically defined} (in short, \emph{geometric}) hypergraphs, and survey many recent coloring results related to them. In particular, we study and survey the following problem, dual to the above covering question. Given a set of points $S$ in the Euclidean space and a family $\mathcal{F}$ of geometric objects of a fixed type, define a hypergraph ${\mathcal H}_m$ on the point set $S$, whose edges are the subsets of $S$ that can be obtained as the intersection of $S$ with a member of $\mathcal F$ and have at least $m$ elements. Is it true that if $m$ is large enough, then the chromatic number of ${\mathcal H}_m$ is equal to 2?
翻译:超图的\\emph{色数}是指对顶点进行着色所需的最小颜色数,使得至少包含两个顶点的边都不是单色的。给定一个覆盖欧几里得空间子集$S$的几何对象族$\\mathcal{F}$,我们可以将其关联到一个超图,其顶点集为$\\mathcal{F}$,边为那些子集${\\mathcal{F}'}\\subset \\mathcal{F}$,其中存在点$p\\in S$使得${\\mathcal F}'$恰好由包含$p$的$\\mathcal{F}$中的元素组成。$\\mathcal{F}$能否被分割成2个覆盖的问题等价于询问该超图的色数是否等于2。对于抽象超图,存在多种色数的竞争概念,这已经引出了深刻的组合问题。本文聚焦于\\emph{几何定义}(简称\\emph{几何})超图,并综述了许多与之相关的最新着色结果。特别地,我们研究并综述了以下与上述覆盖问题对偶的问题:给定欧几里得空间中的点集$S$和固定类型的几何对象族$\\mathcal{F}$,在点集$S$上定义一个超图${\\mathcal H}_m$,其边是$S$的子集,这些子集可以通过$S$与$\\mathcal{F}$中成员的相交获得,且至少包含$m$个元素。是否当$m$足够大时,${\\mathcal H}_m$的色数等于2?