论文标题
无冲突的子集着色
Conflict-Free Colouring of Subsets
论文作者
论文摘要
我们介绍和研究超图中$ t $ subsets的无冲突着色。在这样的颜色中，人们将颜色分配给所有基数的顶点$ t $的子集，使得在任何基础性的高度至少$ t $中都有一个独特的颜色$ t $ -subset。 案例$ t = 1 $，即无顶点无冲突的着色，是一个良好的概念。 $ t = 2 $（即着色对）似乎已经提出了一个新的挑战。用于几何超图的无冲突着色的许多工具都取决于基础超图的遗传性质。在处理顶点子集时，属性不会传递给子集的亚家族。因此，我们开发了可能具有独立利益的新工具。 （i）对于任何固定的$ t $，我们表明，$ \ binom n t $ $ t $ t $ -subsets在飞机上的任何集合$ p $ $ n $点中都可以用$ o（t^2 \ log^2 n）$颜色颜色（t^2 \ log^2 n）颜色，以便至少包含$ p $ $ p $的任何axis-parool-paralitalle矩形，也包含$ p $的$ p $也包含了$ po $ $ t $ t $ t $ t $ t。 （ii）对于一类广泛的“表现良好”的几何定义超图，我们在其$ t $ -subset无冲突的色度上提供了几乎紧密的上限。对于$ t = 2 $，我们表明，对于每个“良好行为”的超图$ h $，通过从$ h $中取出两个超果的HyperGraph $ h'$，承认$ 2 $ -subset的无冲突着色，大致相同的颜色与$ h $相同。 For example, we show that the $\binom n 2$ pairs of points in any set $P$ of $n$ points in the plane can be coloured with $O(\log n)$ colours such that for any two discs $d_1,d_2$ in the plane with $|(d_1\cup d_2)\cap P|\geq 2$ there is a uniquely (in $d_1 \cup d_2$) coloured pair. （iii）我们还表明，在$ t $ - subset无冲突的色号上没有一般绑定，这是$ t = 2 $的标准无冲突色号的函数。
We introduce and study conflict-free colourings of $t$-subsets in hypergraphs. In such colourings, one assigns colours to all subsets of vertices of cardinality $t$ such that in any hyperedge of cardinality at least $t$ there is a uniquely coloured $t$-subset. The case $t=1$, i.e., vertex conflict-free colouring, is a well-studied notion. Already the case $t=2$ (i.e., colouring pairs) seems to present a new challenge. Many of the tools used for conflict-free colouring of geometric hypergraphs rely on hereditary properties of the underlying hypergraphs. When dealing with subsets of vertices, the properties do not pass to subfamilies of subsets. Therefore, we develop new tools, which might be of independent interest. (i) For any fixed $t$, we show that the $\binom n t$ $t$-subsets in any set $P$ of $n$ points in the plane can be coloured with $O(t^2 \log^2 n)$ colours so that any axis-parallel rectangle that contains at least $t$ points of $P$ also contains a uniquely coloured $t$-subset. (ii) For a wide class of "well behaved" geometrically defined hypergraphs, we provide near tight upper bounds on their $t$-subset conflict-free chromatic number. For $t=2$ we show that for each of those "well -behaved" hypergraphs $H$, the hypergraph $H'$ obtained by taking union of two hyperedges from $H$, admits a $2$-subset conflict-free colouring with roughly the same number of colours as $H$. For example, we show that the $\binom n 2$ pairs of points in any set $P$ of $n$ points in the plane can be coloured with $O(\log n)$ colours such that for any two discs $d_1,d_2$ in the plane with $|(d_1\cup d_2)\cap P|\geq 2$ there is a uniquely (in $d_1 \cup d_2$) coloured pair. (iii) We also show that there is no general bound on the $t$-subset conflict-free chromatic number as a function of the standard conflict-free chromatic number already for $t=2$.
