Conflict-Free Colouring of Subsets

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 that originates in the context of frequency allocation to antennas in cellular networks. It has caught the attention of researchers both from the combinatorial and algorithmic points of view. A special focus was given to hypergraphs arising in geometry. 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. For any fixed t, we show that the ntt-subsets in any set P of n points in the plane can be coloured with O(t²log²n) colours so that any axis-parallel rectangle that contains at least t points of P also contains a uniquely coloured t-subset. 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^′, whose hyperedges are obtained by taking all the unions 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 n2 pairs of points in any set P of n points in the plane can be coloured with O(logn) colours such that for any two discs d₁,d₂ in the plane with |(d₁∪d₂)∩P|≥2 there is a uniquely (in d₁∪d₂) coloured pair. 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.