Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 The Problem

A hypergraph is a pair \(\mathcal{H}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}\) is a finite set of nodes and \(\mathcal{E}\) is a family of subsets of \(\mathcal{V}\). The elements of \(\mathcal{E}\) are called the hyperedges of \(\mathcal{H}\). The following concept is the main objective of our study.

Definition 1

k -Strong Conflict-Free (k-SCF) Multicoloring. Let \(\mathcal{H}= (\mathcal{V}, \mathcal{E})\) be a hypergraph, t and k positive integers. A multicoloring of \(\mathcal{H}= (\mathcal{V}, \mathcal{E})\) is a function \(\mathtt{C}: \mathcal{V}\rightarrow 2^{[t]}\) that assigns a subset of \([t]=\{1, \ldots , t\}\) (colors) to each node. The multicoloring \(\mathtt{C}\) is called a k-strong conflict-free multicoloring for \(\mathcal{H}\) if every hyperedge \(E\in \mathcal{E}\) contains at least \(\mu =\min \{|E|, k\}\) distinct nodes \(v_1, \ldots , v_\mu \), such that for each \(i\in \{1, \ldots , \mu \}\) it holds that \(\displaystyle \mathtt{C}(v_i)\not \subseteq \cup _{w \in E \setminus \{ v_i\}} \mathtt{C}(w)\).

In words, a k-SCF multicoloring \(\mathtt{C}\) of \(\mathcal{H}\) is an assignment of a set of colors to each node of \(\mathcal{V}\), such that every hyperedge \(E\in \mathcal{E}\) contains \(\mu =\min \{|E|, k\}\) distinct nodes \(v_1, \ldots , v_\mu \) for which the set of colors \(\mathtt{C}(v_i)\) assigned to any \(v_i\in \{v_1, \ldots , v_\mu \}\) contains at least a color that is not assigned to any other node \(w\in E\setminus \{v_i\}\). In the case of classical hypergraph coloring (i.e., in the case \(|\mathtt{C}(v)|=1\) for each \(v\in \mathcal{V}\)), our definition of k-strong conflict-free multicoloring coincides with the classical definition of k-strong conflict-free coloring [2, 9, 25]. When \(k=1\), our definition reduces to that of conflict-free multicoloring introduced by Even, Lotker, Ron, and Smorodinsky [21] and studied, independently, by Bärtschi and Grandoni [5] and Ghaffari, Kuhn and Maus [23].

In this problem there are two parameters to optimize: the total number of colors, that is, the number t in Definition 1, and the maximum number of colors assigned to any node, that is, the maximum cardinality of the \(\mathtt{C}(v)\)’s. Let \(t(\mathcal{H}, k)\) be the minimum integer t for which a k-SCF multicoloring exists for \(\mathcal{H}\) with t colors. In this paper we derive good upper and lower estimates of \(t(\mathcal{H}, k)\) and of \(\max _v |\mathtt{C}(v)|\).

1.1 Motivations and Previous Work

Classical hypergraph conflict-free coloring (i.e., 1-strong conflict free coloring) was introduced in the geometric setting by Even et al. [21], motivated by a frequency assignment problem in cellular networks. In this scenario, a network consists of fixed-position base stations, that can transmit at a given frequency, and roaming clients. Roaming clients have a range of communication frequencies and come under the influence of different subsets of base stations. Each client can tune to one frequency and receive any message transmitted at that frequency if exactly one station is transmitting at that frequency (if two or more such stations transmit, then interferences destroy the message). The situation can be modeled by means of an appropriate hypergraph coloring. The nodes of the hypergraph correspond to the base stations and the hyperedges correspond to the different subsets of base stations corresponding to receiving ranges of roaming clients. A conflict-free coloring of such a hypergraph corresponds to an assignment of frequencies to the base stations, that enables any client to connect to one of them (the one holding the unique frequency in the client’s range), without interfering with the other base stations. The goal is to minimize the total number of distinct assigned frequencies.

Classical hypergraph conflict-free coloring has been the subject of an intensive study; a survey of the main results in the area is contained in [34]. The theoretical study of conflict-free coloring of general graphs and hypergraphs was initiated in [31] and it has raised much interest due to the novel combinatorial and algorithmic questions it poses; recent results in the area are contained in [5, 6, 9, 22,23,24, 26].

The notion of k-strong conflict free coloring has been studied in [2, 9, 25]. A k-strong conflict free coloring is a coloring that remains conflict-free after any arbitrary collection of \(k-1\) nodes is deleted from the node set of the hypergraph. Thus, a k-strong conflict free coloring for \(k = 1\) is a standard conflict free coloring. The principal motivation to introduce k-strong conflict free coloring was for fault tolerance purposes.

Finally, in the paper [5] the authors introduced the notion of multicoloring (apparently unaware of Sect. 9.2 of [21]). Their motivation was based on the fact that classical hypergraph conflict-free coloring (usually) needs a large number of different colors, and the observation that allowing multiple colors at each node causes a drastic reduction in the total number of needed colors. Hypergraph conflict-free multicoloring appears also in [23].

Additional important motivations to study k-strong conflict-free multicoloring will be highlighted next, after a useful reformulation of the problem. The reformulation of the problem will also be instrumental to put our contributions in the proper context.

1.2 An Equivalent Formulation of Hypergraph Multicoloring

The formulation of k-strong conflict-free multicoloring given in Definition 1 is in the footsteps of the previous nomenclature in the area, and it represents the natural evolution of the concepts of conflict-free coloring [21], k-strong conflict-free coloring [1], and conflict-free multicoloring [5]. In this section we find it convenient to give an equivalent, but more manageable formulation.

Let \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) be a hypergraph, \(n=|\mathcal{V}|\), and \(\mathtt{C}: \mathcal{V}\rightarrow 2^{[t]}\) be a k-strong conflict-free multicoloring for \(\mathcal{H}\). Consider the associated binary matrix M of dimensions \(t\times n\), constructed in the following way: The columns of M are indexed by the nodes in \(\mathcal{V}\) and the generic column of M, indexed by node \(v\in \mathcal{V}\), corresponds to the \(t\times 1\) characteristic vector of subset \(\mathtt{C}(v)\subseteq [t]\). In other words, \(M[i,j]=1\) if color \(i\in \mathtt{C}(v_j)\), and \(M[i,j]=0\) if color \(i\notin \mathtt{C}(v_j)\). For any hyperedge \(E\in \mathcal{E}\), let us denote by M(E) the \(t\times |E|\) submatrix consisting of all columns in M whose indices (nodes) belong to E. From Definition 1 of k-SCF multicoloring, it is immediate to see that the matrix M enjoys the following property:

for each \(E \in \mathcal{E}\), the submatrix M(E) contains at least \(\min \{|E|, k\}\) pairwise different rows, each of Hamming weight Footnote 1 exactly equal to 1 (we shall denote such rows as unit rows).

Viceversa, it is also immediate to see that any \(t\times n\) matrix M that satisfies above property gives rise to a k-strong conflict-free multicoloring \(\mathtt{C}\) for \(\mathcal{H}=(\mathcal{V},\mathcal{E})\), \(|\mathcal{V}|=n\), using a total number of colors equal to t. Indeed, the set of colors assigned to each \(v_j\in \mathcal{V}\) is \(\mathtt{C}(v_j)=\{i \ : \ M[i,j]=1\}\). For the sake of brevity, matrices with the above property will be called k-SCF matrices of size t.

1.3 Our results in perspective

Our main result is presented in Theorem 2. It gives an algorithm that, for any parameter \(k\ge 1\) and input hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\), \(|\mathcal{V}|=n\), returns a k-SCF multicoloring of \(\mathcal{H}\) such that:

  • the total number of colors is

    $$\begin{aligned} O(\min \{ (k+\log \frac{r}{k} )\log {\varGamma }+ k(k+\log ^2 \frac{r}{k} ) , \ (k^2 + r ) \log n \}); \end{aligned}$$

  • the expected number of colors per node is \(O(\min \{k+\log {\varGamma }, \ (k + \log \frac{r}{k}) \log n \})\),

where \({\varGamma }=\max _{E \in \mathcal{E}}|\{E'\, :\, E'\in \mathcal{E}, E\cap E'\ne \emptyset \}|\) and \(r=\max _{E \in \mathcal{E}} |E|\) are the maximum hyperedge degree and hyperedge size of \(\mathcal{H}\), respectively. The algorithm can be transformed into a Las Vegas algorithm that guarantees the claimed number of colors per node with a standard argument.

To see the relevance of our findings, we instantiate some of them to the particular case of \(k=1\) (see Theorem 3) and we compare to corresponding results in the literature. The authors of [5] gave a Las Vegas algorithm for 1-SCF multicoloring of a hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\), that uses \(O(\log n \log {\varGamma })\) total number of colors and \(O(\min \{\log {\varGamma }, \log n \log \log {\varGamma }\})\) colors per node. Under the same hypothesis and defining \(\rho =\frac{\max _{E\in \mathcal{E}} |E|}{\min _{E\in \mathcal{E}} |E|}\), our algorithm uses \(O(\min \{\log (\rho +1) \log {\varGamma }, r \log n \})\) total number of colors and \(O(\min \{\log {\varGamma }, \log n \log (\rho +1)\})\) colors per node. It is clear that our upper bound on the total number of colors is always better than that of [5]. In general, our bound on the number of colors per node is not confrontable with the corresponding bound of [5], in the sense that for some values of the involved parameters ours is better, for others the bound of [5] is better. Moreover, if the hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) is such that \({\varGamma }\) is polynomial in \(n=|\mathcal{V}|\) and \(\rho =O(1)\), our Theorem 3 implies that there exists a 1-SCF multicoloring of \(\mathcal{H}\) with a \(O(\log n)\) total number of color, implying the corresponding result in [23].

However, and much more importantly, our framework constitutes a far reaching generalization of several algorithmic and combinatorial questions widely studied in the literature. To see this, consider the case in which \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) is the complete r-uniform regular hypergraph. In other words, the set of hyperedges \(\mathcal{E}\) coincides with all the \({n\atopwithdelims ()r}\) subsets of cardinality r of \(\mathcal{V}\). In this case, one can easily see that the definition of r-SCF matrices coincides with that of superimposed codes [27] (also known as cover-free families [20], strongly selective families [11], disjunct matrices [14]). Informally, a (r, n)-superimposed code is a \(t\times n\) binary matrix such that for any r columns of the matrix and for any column \(\mathbf{c}\) chosen among these r columns, there exists a row in correspondence of which \(\mathbf{c}\) has an entry equal to 1 and the remaining \(r-1\) columns have entries equal to 0. Superimposed codes represent the main tool for the efficient solution of problems arising in an surprising variety of areas: compressed sensing [12], cryptography and data security [28], pattern matching [32], distributed colouring [29], secure distributed computation [7], groupo testing [14, 15] and circuit complexity [8], among the others. Additionally, k-SCF matrices for the complete r-uniform regular hypergraph \(\mathcal{H}\), \(1\le k\le r\), coincide with the (k, r, n)-selectors of [10, 13], another combinatorial structure that has found many applications in several different areas. One can also see that 1-SCF matrices for the complete r-uniform regular hypergraph \(\mathcal{H}\) coincide with the locally thin families of [3]. The last equivalences will be used to exploit known non-existential results for (k, r, n)-selectors and locally thin families to prove lower bounds on the number of colors needed in k-SCF hypergraph multicoloring. Some of these obtained lower bounds improve on the corresponding results for hypergraph multicoloring given in [5], and they show that our results are not too far from being optimal.

We believe that this is one of the main conceptual contribution of this paper, that is, a general framework where to formulate a host of different combinatorial problems. For the sake of definiteness, in this version of the paper we only focus on the hypergraph multicoloring problem.

2 Mathematical preliminaries

In this section, we give an upper bound on the number of rows (size) of a k-SCF matrix for certain hypergraphs \(\mathcal{H}=(\mathcal{V},\mathcal{E})\). By the observations made in Sect. 1.2, this gives an upper bound on the minimum number of colors \(t(\mathcal{H}, k)\) in any k-strong conflict-free multicoloring for \(\mathcal{H}\). The obtained results will be used in Sect. 3 to get a k-SCF multicoloring for a generic hypergraph.

Let \(r\) be the maximum size of any hyperedge (i.e., \(2 \le |E| \le r\) for each \(E \in \mathcal{E}\)) and \({\varGamma }=\max _{E \in \mathcal{E}}|\{E'\, :\, E'\in \mathcal{E}, E\cap E'\ne \emptyset \}|\) be the maximum hyperedge degree of \(\mathcal{H}\). In order to prove our main results, we need to recall the celebrated Lovász Local Lemma for the symmetric case (see [4]), as stated below.

Lemma 1

Let \(A_{1},A_{2},\ldots ,A_{b}\) be events in an arbitrary probability space. Suppose that each event \(A_{i}\) is mutually independent of a set of all the other events \(A_{j}\) except for at most d, and that \(\Pr (A_{i})\le P\) for all \(1\le i\le b\). If \(eP(d+1)\le 1\), then \(\Pr (\cap _{i=1}^{n}\bar{A_{i}})>0\), where \(e=2.71828\ldots \) is the base of the natural logarithm.

Using Lemma 1 we can prove the following result.

Lemma 2

Let \(k >1\) and let \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) be a hypergraph whose hyperedges have size at most k. There exists a k-SCF matrix M for \(\mathcal{H}\) of size

$$\begin{aligned} c = \lceil e k \ (\log [e({\varGamma }+1)] + \log k )\rceil . \end{aligned}$$
(1)

Proof

Let \(M=[M(i,j)]\) be a random binary \(c\times n\) matrix such that all entries in M are chosen independently, with probabilities

$$Pr\left( M(i,j)=0\right) =p=1 - {1}/{k}, \quad \text{ and } Pr\left( M(i,j)=1\right) =1-p= {1}/{k}.$$

We prove that for \(c=\lceil e k \ (\log [e({\varGamma }+1)] + \log k )\rceil \), with positive probability M is a k-SCF matrix for \(\mathcal{H}\). In particular, since each edge \(E \in \mathcal{E}\) has cardinality \(|E|\le k\), we prove that with positive probability all the submatrices M(E), \(E\in \mathcal{E}\), contain all the |E| pairwise different unit rows.

For a fixed \(E \in \mathcal{E}\), let us consider the “bad” event \(F_E\) that the submatrix M(E) does not contain all the |E| unit rows. Fix a unit vector of length |E| (i.e., a vector of length |E| and Hamming weight 1) and an index \(j\in \{1, \ldots , c\}\). Let \(R_j\) be the event that the row j of the submatrix M(E) does not match the fixed unit vector; we have that

$$Pr(R_j) = 1-(1-p)p^{|E|-1}.$$

The probability of the event \(R_E\) that none of the rows of the submatrix M(E) matches the fixed unit vector is then

$$Pr(R_E) = Pr(R_{1} \wedge \ldots \wedge R_{c})= (1-p^{|E|-1}(1-p))^{c}.$$

Consider the event \(F_E\) that the submatrix M(E) does not contain all the |E| unit rows. In such a case there exists a unit vector that does not appear as a row of M(E). From this, by using the union bound we can estimate the probability of \(F_E\) as

$$\begin{aligned} Pr(F_E) \le |E| \, Pr(R_E) = |E| (1-p^{|E|-1}(1-p))^{c}. \end{aligned}$$

Recalling that \(|E| \le k\) and \(p=1 - \frac{1}{k}\), and using the inequality \((1-\frac{1}{k})^{k-1} > \frac{1}{e}\), where e is the base of the natural logarithm, we get that

$$\begin{aligned} Pr(F_E)\le k \left( 1- \left( 1- \frac{1}{k}\right) ^{k-1}\frac{1}{k} \right) ^{c} < k \left( 1- \frac{1}{e k} \right) ^{c}. \end{aligned}$$
(2)

We notice now that two events \(F_E\) and \(F_{E'}\), for \(E, E' \in \mathcal{E}\), are independent unless \(E \cap E' \ne \emptyset \). For each \(F_E\), the number of events \(F_{E'}\) for which \(E \cap E' \ne \emptyset \) is upper bounded by the maximum hyperedge degree \({\varGamma }\) of \(\mathcal{H}\). Lemma 1 tells us that if the upper bound \(k \left( 1- \frac{1}{e k} \right) ^{c}\) in (2) and the quantity \({\varGamma }\) satisfy the relation

$$\begin{aligned} e\left[ k \left( 1- \frac{1}{e k} \right) ^{c}\right] ({\varGamma }+1) \le 1 \end{aligned}$$
(3)

then the probability that none of the “bad” events \(F_E\) occur, for \(E\in \mathcal{E}\), is strictly positive. That is, there is a strictly positive probability that for each \(E\in \mathcal{E}\) the submatrix M(E) contains all the |E| pairwise different unit rows. Computing the minimum c for which (3) holds (here we also use the well known inequality \(\ln x\le x-1\), for any \(x>0\)), we get the desired value in (1).    \(\square \)

Lemma 3

Let \(k \ge 1\) and \(i \ge \lfloor \log k\rfloor +1\). Let \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) be a hypergraph where the cardinality |E| of each hyperedge \(E\in \mathcal{E}\) is such that \(\max \{ k,2^{i-1} \}<|E|\le 2^i\). There exists a k-SCF matrix M for \(\mathcal{H}\) of size

$$\begin{aligned} c_i = {\left\{ \begin{array}{ll}\displaystyle \left\lceil 2e k \left( \log [e({\varGamma }+1)] + \log {2^{\lfloor \log k\rfloor +1} \atopwithdelims ()2^{\lfloor \log k\rfloor }} \right) \right\rceil &{} \text{ if } i = \lfloor \log k\rfloor +1 \\ \\ \displaystyle \left\lceil \frac{e2^i}{2^{i-1}-k+1} \left( \log [e({\varGamma }+1)] + \log {2^i \atopwithdelims ()k-1} \right) \right\rceil &{} \text{ otherwise. } \end{array}\right. } \end{aligned}$$
(4)

Proof

Fix \(i \ge \lfloor \log k\rfloor +1\). We construct a random \(c_i\times n\) binary matrix M, where each element is generated independently and assumes value 0 with probability \(p=(2^i-1)/2^i\).

Fix a hyperedge \(E \in \mathcal{E}\) (recall that \(|E|>k\)). For any set R of \(|E|-k+1\) unit vectors of length E, let \(A_{R,E}\) be the event that none of the vectors in R appears as a row in M(E). The probability of such an event is

$$\begin{aligned} Pr(A_{R,E})=(1-(|E|-k+1)p^{|E|-1}(1-p))^{{c^{}_i}}. \end{aligned}$$
(5)

Let \(\mathcal {R}\) be the family of all the \(t={|E| \atopwithdelims ()|E|-k+1}\) possible sets of exactly \(|E|-k+1\) unit vectors of length |E|. The probability of the event \(A_E\) that the submatrix M(E) does not contain any of the rows of some \(R\in \mathcal {R}\) is

$$\begin{aligned} Pr(A_E) = Pr\left( \bigvee _{R\in \mathcal {R}} A_{R,E}\right) \le {|E| \atopwithdelims ()|E|-k+1} (1-(|E|-k+1)p^{|E|-1}(1-p))^{{c^{}_i}}, \end{aligned}$$
(6)

where the inequality is due to the union bound and (5). From this we get

$$\begin{aligned} Pr(A_E)\le & {} {2^i \atopwithdelims ()2^i-k+1} \left( 1-(|E|-k+1)\left( 1-\frac{1}{2^i}\right) ^{2^i-1}\frac{1}{2^i}\right) ^{{c^{}_i}} \end{aligned}$$
(7)
$$\begin{aligned}< & {} {2^i \atopwithdelims ()2^i-k+1} \left( 1-(|E|-k+1)\frac{1}{e 2^i}\right) ^{{c^{}_i}} \end{aligned}$$
(8)

where inequality (7) is obtained from (6) by recalling that \(p=(1-\frac{1}{2^i})\) and \(|E| \le 2^i\), (8) follows from (7) by recalling that \((1-\frac{1}{2^i})^{2^i-1} > \frac{1}{e}\).

We now further refine the bound in (8) and show that for each \(E \in \mathcal{E}\) it holds

$$\begin{aligned} Pr(A_E) \le q_i= {\left\{ \begin{array}{ll} \displaystyle {{2^{\lfloor \log k\rfloor +1}\atopwithdelims ()2^{\lfloor \log k\rfloor } }\left( 1-\frac{1}{e 2^{\lfloor \log k\rfloor +1}}\right) ^{{c^{}_{\lfloor \log k\rfloor +1}}} }&{}{\text{ if }\,\, i=\lfloor \log k\rfloor +1}\\ \\ \displaystyle {2^i \atopwithdelims ()k-1} \left( 1-(2^{i-1}-k+1)\frac{1}{e 2^i}\right) ^{{c^{}_i}} &{}{\text{ otherwise. }} \end{array}\right. } \end{aligned}$$
(9)

If \(i=\lfloor \log k\rfloor +1\) then for \(E \in \mathcal{E}\) it holds \(2^{\lfloor \log k\rfloor } \le k < |E| \le 2^{\lfloor \log k\rfloor +1}\), and we get \({2^{\lfloor \log k\rfloor +1} \atopwithdelims ()2^{\lfloor \log k\rfloor +1}-k+1} \le {2^{\lfloor \log k\rfloor +1} \atopwithdelims ()2^{\lfloor \log k\rfloor }}\). Furthermore, \(|E|-k+1 \ge 1\) and (9) holds.

If \(i \ge \lfloor \log k\rfloor +2\), then for \(E \in \mathcal{E}\) we have \(k< 2^{i-1} < |E| \le 2^i\) and (9) holds.

Denote now by \(F_E\) the event that the matrix M(E) does not contain at least k pairwise different unit rows. One can see that \(Pr(F_E) = Pr(A_E)\). Indeed, if M(E) did not contain at least k pairwise different unit rows, then it would exist a set \(R\in \mathcal {R}\), made by \(|E|-(k-1)\) unit vectors, none of them being a row of M(E). As a consequence, we have

$$Pr(F_E) = Pr(A_E) \le q_i.$$

Moreover, two events \(F_E\) and \(F_{E'}\), for \(E, E' \in \mathcal{E}\), are independent whenever \(E \cap E' =\emptyset \). Therefore, each event \(F_E\) is dependent on at most \({\varGamma }\) other events (recall that \({\varGamma }\) is the maximum hyperedge degree of \(\mathcal{H}\)). According to Lemma 1, if the parameters \(q_i\) (defined in (9)) and \({\varGamma }\) satisfy

$$\begin{aligned} eq_i ({\varGamma }+1) \le 1 \end{aligned}$$
(10)

then there is a strictly positive probability that for each \(E\in \mathcal{E}\) the submatrix M(E) contains at least k pairwise different unit rows. To conclude the proof, we compute the minimum \({c^{}_i}\) such that (10) holds.

  • In case \(i=\lfloor \log k\rfloor +1\), formula (10) becomes

    $$e ({\varGamma }+1) {2^{\lfloor \log k\rfloor +1} \atopwithdelims ()2^{\lfloor \log k\rfloor }} \left( 1-\frac{1}{e 2^{\lfloor \log k\rfloor +1}}\right) ^{{c^{}_{\lfloor \log k\rfloor +1}}} \le 1$$

    and we get

    $$c_{\lfloor \log k\rfloor +1} \le \left\lceil e 2^{\lfloor \log k\rfloor +1} \left( \log [e({\varGamma }+1)] + \log {2^{\lfloor \log k\rfloor +1} \atopwithdelims ()2^{\lfloor \log k\rfloor }} \right) \right\rceil $$

  • If \(i \ge \lfloor \log k\rfloor +2\) then (10) becomes

    $$e ({\varGamma }+1) {2^i \atopwithdelims ()k-1} \left( 1-(2^{i-1}-k+1)\frac{1}{e 2^i}\right) ^{{c^{}_i}} \le 1.$$

All together, we get (4).    \(\square \)

3 Strong Conflict-Free Multicoloring Algorithm

In this section we present a k-SCF multicoloring algorithm for a generic hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\). Our algorithm works as follows: We first partition the hypergraph \(\mathcal{H}\) into \(\lceil \log r\rceil -\lfloor \log k\rfloor \) almost uniform sub-hypergraphs, where \(r=\max _{E \in \mathcal{E}} |E|\). Successively, we apply Lemmas 2 and 3 to construct k-SCF multicolorings for each of these sub-hypergraphs. Finally, we combine the obtained multicolorings into a global k-SCF multicoloring for \(\mathcal{H}\).

We split the hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) into appropriate sub-hypergraphs, as follows: We partition the hyperedge set \(\mathcal{E}\) into disjoint sets

$$\begin{aligned} \mathcal{E}^{'}= & {} \{ E \ : \ E \in \mathcal{E}, \ |E|\le k\} \; \text{ and } \\ \mathcal{E}^{''}_{i}= & {} \{ E \ : \ E \in \mathcal{E}\setminus \mathcal{E}^{'}, \ 2^{i-1} <|E|\le 2^i\}, \text{ for }\,\, i=\lfloor \log k\rfloor +1, \ldots , \lceil \log r\rceil . \end{aligned}$$

For each set in the resulting partition of \(\mathcal{E}\), we consider the associated induced sub-hypergraph, namely:

$$\begin{aligned} \mathcal{H}^{'}=(\mathcal{V},\mathcal{E}^{'}) \text{ and } \mathcal{H}^{''}_{i}=(\mathcal{V},\mathcal{E}^{''}_{i}), \text{ for } i=\lfloor \log k\rfloor +1, \ldots , \lceil \log r\rceil . \end{aligned}$$
(11)

Notice that \(\mathcal{E}'\) or some \(\mathcal{E}^{''}_{i}\) in the above partition of \(\mathcal{E}\) could be empty; in particular, if \(k=1\) then \(\mathcal{E}'\) is empty and the hypergraph \(\mathcal{H}'\) is not defined.

The results in Lemmas 2 and 3 imply the existence of k-SCF matrices (multicolorings) for the hypergraphs in (11), with number of rows (i.e., total number of colors used) given by (1) and (4).

To convert such results into an efficient algorithm to construct a \(k-\)SCF-multicoloring of the input hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) we first invoke important result of Moser and Tardos [30], summarized in the following theorem.

Theorem 1

([30]). Let P be a finite set of mutually independent random variables in a probability space. Let \(\mathcal{A}\) be a finite set of events determined by these variables. For \(A \in \mathcal{A}\), let \({\varGamma }(A)\) be a subset of \(\mathcal{A}\) satisfying that A is independent from the collection of events \(\mathcal{A}\setminus (\{A\} \cup {\varGamma }(A))\). If there exists an assignment of reals \(y : A \mapsto (0, 1)\) such that

$$\forall A\in \mathcal{A}\quad Pr(A) \le y(A) \prod _{B \in {\varGamma }(A)} (1-y(B)),$$

then there exists an assignment of values to the variables P not violating any of the events in \(\mathcal{A}\). Moreover, there exists an algorithmFootnote 2 that resamples an event \(A\in \mathcal{A}\) at most an expected \(y(A)/(1 -y(A))\) times before it finds such an evaluation. Thus the expected total number of resampling steps is at most \(\sum _{A\in \mathcal{A}} y(A)/(1 - y(A))\).

One can see that the events \(F_E\) defined in Lemmas 2 and 3 satisfy the hypothesis of Theorem 1 with \(y(F_E)= \frac{1}{{\varGamma }+1}\). We are then ready to present our algorithm to produce a k-SCF multicoloring algorithm for a general hypergraph \(\mathcal{H}\). The algorithm is described below:

  1. 1.

    We first partition the input hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) into the sub-hypergraphs defined in (11), namely:

    $${\mathcal{H}^{'}=(\mathcal{V},\mathcal{E}^{'}), \ \mathcal{H}^{''}_{\lfloor \log k\rfloor +1}=(\mathcal{V},\mathcal{E}^{''}_{\lfloor \log k\rfloor +1}), \ldots , \mathcal{H}^{''}_{\lceil \log r\rceil }=(\mathcal{V},\mathcal{E}^{''}_{\lceil \log r\rceil })}.$$
  2. 2.

    Successively, we generate the respective k-SCF matrices:

    $${M}^{'},\ {M}^{''}_{\lfloor \log k\rfloor +1},\ \ldots , {M}^{''}_{\lceil \log r\rceil }$$

    according to Theorem 1.

    (We recall that some of the matrices can be non existent in case the corresponding hypergraph contains no hyperedge and that their sizes, denoted by \(c^{'}, c^{''}_{\lfloor \log k\rfloor +1}, \ldots , c^{''}_{\lceil \log r\rceil }\) are bounded according to Lemmas 2 and 3).

    The obtained matrices are now “juxtaposed” one on top of the others, to obtain a matrix M. It is not hard to see that M is a k-SCF matrix for the original hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\).

  3. 3.

    The set of colors assigned to each \(v \in V\) is then obtained from the column corresponding to v in each of the matrices \({M}^{'}, {M}^{''}_{\lfloor \log k\rfloor +1}, \ldots , {M}^{''}_{\lceil \log r\rceil }\), collecting the indices of the rows in which 1 appears. Hence, the set of colors \(\mathtt{C}(v)\) assigned to each node \(v \in V\) is

$$\begin{aligned} \mathtt{C}(v) = {\left\{ \begin{array}{ll} \mathop {\bigcup }\nolimits _{i=\lfloor \log k\rfloor +1}^{\lceil \log r\rceil }\left\{ \left( c'+\mathop {\sum }\nolimits _{j=\lfloor \log k\rfloor +1}^{i-1} c^{''}_j\right) +h \ | \ {M}^{''}_{i}[h,v]=1\right\} \cup &{} \left\{ h \ | \ {M}^{'}[h,v]=1\right\} \\ &{}\qquad \qquad \text{ if }\,\, k>1,\\ \mathop {\bigcup }\nolimits _{i=\lfloor \log k\rfloor +1}^{\lceil \log r\rceil }\left\{ \left( \mathop {\sum }\nolimits _{j=\lfloor \log k\rfloor +1}^{i-1} c^{''}_j\right) + h \ | \ {M}^{''}_{i}[h,v]=1\right\} &{} \quad \qquad \text{ otherwise. } \end{array}\right. } \end{aligned}$$

Theorem 2

Given a hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\), the above algorithm returns a k-SCF multicoloring for \(\mathcal{H}\) such that

  1. (i)

    the expected number of resampling steps is at most \(|\mathcal{E}|/ {\varGamma }\),

  2. (ii)

    the total number of colors is

    $$c(\mathcal{H})=O\left( \min \left\{ \displaystyle \left( k+\log \frac{r}{k}\right) \log {\varGamma }+ k \left( k+ \log ^2 \frac{r}{k} \right) , \ (k^2 + r ) \log n \right\} \right) ,$$
  3. (iii)

    the expected number of colors per node is \(\displaystyle O(\min \{k+\log {\varGamma }, \ (k + \log \frac{r}{k}) \log n \})\).

where \(n=|\mathcal{V}|\), \(r=\max _{E \in \mathcal{E}} |E|\), and \({\varGamma }\) is the maximum hyperedge degree.

Proof

Recall that \(\mathcal{E}= (\cup _{i=\lfloor \log k\rfloor +1}^{\lceil \log r\rceil } {\mathcal{E}''_i})\cup \mathcal{E}'\) and \({y(F_E)}/({1-y(F_E)})={1}/{{\varGamma }}\), for each \(E\in \mathcal{E}\). Theorem 1 implies that the sum over each sub-hypergraph of the expected number of resampling steps is at most \(\frac{|\mathcal{E}'|}{{\varGamma }}+\sum _{i=\lfloor \log k\rfloor +1}^{\lceil \log r\rceil } \frac{|\mathcal{E}''_i|}{{\varGamma }}=\frac{|\mathcal{E}|}{{\varGamma }}\).

We evaluate now the number of colors \(c(\mathcal{H}) = c' + \sum _{i=\lfloor \log k\rfloor +1}^{\lceil \log r\rceil } c^{''}_i\) that the algorithm uses. Here, \(\varGamma '\) and \(\varGamma _i\), for \(i=\lfloor \log k\rfloor +1,\ldots , \lceil \log r\rceil \), denote the maximum hyperedge degree of \(\mathcal{H}^{'}\) and \(\mathcal{H}^{''}_{i}\), respectively.

  • By (1) we get

    $$\begin{aligned} c'<e k \ (\log [e({\varGamma }'+1)]+ \log k ) +1. \end{aligned}$$
    (12)

  • For \(i={\lfloor \log k\rfloor +1}\), by (4) and noticing that \(\log {2^{\lfloor \log k\rfloor +1} \atopwithdelims ()2^{\lfloor \log k\rfloor }} \le 2^{\lfloor \log k\rfloor +1} \le 2k\), we get

    $$\begin{aligned} c^{''}_{\lfloor \log k\rfloor +1} < 2e k \left( \log [e({\varGamma }_{\lfloor \log k\rfloor +1}+1)] + 2k \right) +1 . \end{aligned}$$
    (13)

  • For \(i={\lfloor \log k\rfloor +2}\), by (4) we get

    $$\begin{aligned} c^{''}_{\lfloor \log k\rfloor +2} < 2e k \left( \log [e({\varGamma }_{\lfloor \log k\rfloor +2}+1)] + (k-1) \log 8e \right) +1. \end{aligned}$$
    (14)

  • For any \(i=\lfloor \log k\rfloor +3,\ldots , \lceil \log r\rceil \), by Lemma 3 we have

    $$\begin{aligned} {c^{}_i}^{''}= & {} \left\lceil \frac{e2^i}{2^{i-1}-k+1} \left( \log [e({\varGamma }_i+1)] + \log {2^i \atopwithdelims ()k-1} \right) \right\rceil \\< & {} 1 + \frac{e2^i}{2^{i-1}-k+1} \left( \log [e({\varGamma }_i+1)] + (k-1)\log \frac{e2^i}{k-1} \right) \\< & {} 1 + \frac{e2^i}{2^{i-1}-k+1} \left( \log [e({\varGamma }_i+1)] + (k-1)\log \frac{2er}{k-1} \right) . \end{aligned}$$

    By noticing that \(\lfloor \log k\rfloor +3\le i\) implies that \(\frac{2^i}{2^{i-1}-k+1} < 4\), we obtain

    $$\begin{aligned} {c^{}_i}^{''} < 1 + 4e \left( \log [e({\varGamma }_i+1)] + (k-1)\log \frac{e2r}{k-1} \right) \end{aligned}$$
    (15)

Summarizing form (12), (13), (14) and (15) we have

$$\begin{aligned} c(\mathcal{H})= & {} c' + c^{''}_{\lfloor \log k\rfloor +1} + c^{''}_{\lfloor \log k\rfloor +2} + \sum _{i=\lfloor \log k\rfloor +3}^{\lceil \log r\rceil } c^{''}_i \\< & {} e k \ (\log [e({\varGamma }'+1)]+ \log k ) + 2ek (\log [e({\varGamma }_{\lfloor \log k\rfloor +1}+1)] + 2k ) \nonumber \\&+ 2e k (\log [e({\varGamma }_{\lfloor \log k\rfloor +2}+1)] + (k-1) \log 8e) \nonumber \\&+ 4e \sum _{i=\lfloor \log k\rfloor +3}^{\lceil \log r\rceil } \log [e({\varGamma }_i+1)] + O(k \log ^2 \frac{r}{k}) \nonumber \end{aligned}$$
(16)

In order to get (ii), we derive two upper bounds on \(c(\mathcal{H})\).

  • We first notice that both

    $$\begin{aligned} {\varGamma }'\le {\varGamma }\quad \text{ and } \quad {\varGamma }_i \le {\varGamma }, \text{ for } i=\lfloor \log k\rfloor +1,\ldots , \lceil \log r\rceil . \end{aligned}$$
    (17)

    Hence, from (16) we get \(\displaystyle c(\mathcal{H}) =O\left( \left( \log \frac{r}{k}+ k\right) \log {\varGamma }+ k \left( \log ^2 \frac{r}{k} +k\right) \right) .\)

  • On the other hand, each hyperedge in \(\mathcal{E}'\) has size at most k and those in \(\mathcal{E}''_i\), for \(i=\lfloor \log k\rfloor +1, \ldots , \lceil \log r\rceil \), have size at most \(2^i\). This implies that

    $$\begin{aligned} {\varGamma }'\le |\mathcal{E}'|\le n^{k} \ \text{ and } \ {\varGamma }_i\le |\mathcal{E}''_i|\le n^{2^i} \text{ for } i=\lfloor \log k\rfloor +1,\ldots , \lceil \log r\rceil . \end{aligned}$$
    (18)

    As a consequence, all the quantities \(\log {\varGamma }' \), \(\log ({\varGamma }_{\lfloor \log k\rfloor +1})\) and \(\log ({\varGamma }_{\lfloor \log k\rfloor +2})\) are bounded above by \(k \log n\). Additionally

    $$\sum _{i=\lfloor \log k\rfloor +3}^{\lceil \log r\rceil } \log [e({\varGamma }_i+1)] \le \sum _{i=\lfloor \log k\rfloor +3}^{\lceil \log r\rceil } \log [e(n^{2^i}+1)] = O(r \log n).$$

    By this and (16), we obtain the bound \(c(\mathcal{H}) =O((k^2 + r ) \log n)\).

Finally we prove (iii). Consider any node \(v \in V\). Recalling that in Lemma 2 we set \(Pr({M}^{'}[h,v]=1)=1/k\) and in Lemma 3 we set \(Pr({M}^{''}_{i}[h,v]=1)=1/2^i\), for \(i=\lfloor \log k\rfloor +1, \ldots , \lceil \log r\rceil \), we have that the expected number of colors \(|\mathtt{C}(v)|\) assigned to v is

$$\begin{aligned} |\mathtt{C}(v)|= & {} c' \frac{1}{k} + \sum _{i=\lfloor \log k\rfloor +1}^{\lceil \log r\rceil } c^{''}_i \frac{1}{2^i} \\\le & {} \frac{1}{k} \lceil e k \ (\log [e({\varGamma }'+1)] + \log k ) \rceil + \frac{1}{k} \lceil 2e k (\log [e({\varGamma }_{\lfloor \log k\rfloor +1}+1)]+ 2k ) \rceil \\&+ \frac{1}{2k} \lceil 2e k (\log [e({\varGamma }_{\lfloor \log k\rfloor +2}+1)] + (k-1) \log 8e )\rceil \\&+ \sum _{i=\lfloor \log k\rfloor +3}^{\lceil \log r\rceil } \frac{1}{2^i}\left\lceil \frac{e2^i}{2^{i-1}-k+1} \left( \log [e({\varGamma }_i+1)] + \log {2^i \atopwithdelims ()k-1} \right) \right\rceil \\\le & {} e \ (\log [e({\varGamma }'+1)]+ \log k ) + e 2 (\log [e({\varGamma }_{\lfloor \log k\rfloor +1}+1)] + 2k ) \\&+ e (\log [e({\varGamma }_{\lfloor \log k\rfloor +2}+1)] + (k-1) \log 8e )+ \frac{3}{k} \\&+ \sum _{i=\lfloor \log k\rfloor +3}^{\lceil \log r\rceil } \frac{1}{2^i} \left[ 2 + 4e \left( \log [e({\varGamma }_i+1)] + (k-1) \log \frac{e2^i}{k-1} \right) \right] \end{aligned}$$

From this, by using the bound in (17) we get \(|\mathtt{C}(v)| =O(k+\log {\varGamma })\). Moreover, by (18) we get \(|\mathtt{C}(v)| =O\left( \left( k + \log \frac{r}{k}\right) \log n \right) \).    \(\square \)

3.1 1-SCF Multicoloring

In case of 1-SCF Multicoloring, from Lemma 3 we get that for any \(i\le \lceil \log r\rceil \), there exists a 1-SCF matrix, for the sub-hypergraph induced by the edges of size in \(\{2^{i-1}+1,\ldots , 2^{i}\}\), of size \( \left\lceil 2 e\left( \log ({\varGamma }_i+1) +1 \right) \right\rceil .\) From this, we have that the number of colors that the algorithm uses in such a case is

$$\begin{aligned} c(\mathcal{H}) = \sum _{i=\lfloor \log k\rfloor +1 }^{\lceil \log r\rceil } c^{''}_i= \sum _{\begin{array}{c} i=1\\ \mathcal{E}''_i\ne \emptyset \end{array} }^{\lceil \log r\rceil }\left\lceil 2 e\left( \log ({\varGamma }_i +1) +1 \right) \right\rceil . \end{aligned}$$
(19)

Furthermore, the expected number of colors assigned to an arbitrary node v is

$$\begin{aligned} |\mathtt{C}(v)| = \sum _{i=\lfloor \log k\rfloor +1 }^{\lceil \log r\rceil } \frac{1}{2^i} \ c^{''}_i= \sum _{\begin{array}{c} i=1\\ \mathcal{E}''_i\ne \emptyset \end{array} }^{\lceil \log r\rceil }\frac{1}{2^i} \left\lceil 2 e\left( \log ({\varGamma }_i +1) +1 \right) \right\rceil . \end{aligned}$$
(20)

By using (17) and (18) to bound (19) and (20), we have the following result.

Theorem 3

Let \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) and \(\rho =\frac{\max _{E\in \mathcal{E}} |E|}{\min _{E\in \mathcal{E}} |E|}\). The hypergraph \(\mathcal{H}\) admits a 1-SCF multicoloring with \(O(\min \{\log (\rho +1) \log {\varGamma }, r \log n \})\) total number colors and \(O(\min \{\log {\varGamma }, \log n \log (\rho +1)\}) \) colors per node.

4 Lower Bounds

In this section we provide some lower bounds on the minimum integer t for which a k-strong conflict-free multicoloring \(\mathtt{C}: \mathcal{V}\rightarrow 2^{[t]}\) exists for the hypergraph \(\mathcal{H}=(\mathcal{V},\mathcal{E})\). In other words, we seek lower bounds on the parameter \(t(\mathcal{H}, k)\).

Denote by \(\mathcal{H}^n_r=(\mathcal{V},\mathcal{E})\) the complete r-uniform hypergraph on n nodes. We recall that in this case \(\mathcal{E}\) coincides with all the \({n\atopwithdelims ()r}\) subsets of cardinality r of \(\mathcal{V}\), \(n=|\mathcal{V}|\). Bärtschi and F. Grandoni [5] proved that \(t(\mathcal{H}^n_r, 1)=\varOmega (\log n)\). By using a deep theorem from [3], we can improve the above result. We first recall the following definition from [3]. A family \(\mathcal{F}\) of subsets of the ground set [t] is r-locally thin if for any r of its distinct member sets at least one point \(i\in [t]\) is contained in exactly one of them. Let N(r, t) be the maximum cardinality of any r-locally thin family over the ground set [t]. Alon et al. [3] proved that for any \(r>2\) it holds

$$\begin{aligned} \limsup _{t\rightarrow \infty } \frac{1}{t}\log N(r,t)\le {\left\{ \begin{array}{ll} 2/r &{} \text { if } r \text { is even, }\\ {(2\log r)}/{r} &{} \text { otherwise}. \end{array}\right. } \end{aligned}$$
(21)

An alternative way to see r-locally thin families is the following. Let us associate to the family \(\mathcal F\) the binary matrix M whose columns are the characteristic vectors of the sets \(F\in \mathcal{F}\). It is clear that the matrix M enjoys the following property: For each r-tuple A of columns of M there exists a unit row in M(A). By using the equivalence between k-SCF multicoloring and k-SCF matrices, that we have established in Sect. 1.2, and formula (21), we get that for any \(r>2\) it holds

$$\begin{aligned} t(\mathcal{H}^n_r, 1)={\left\{ \begin{array}{ll} \varOmega \left( r\log n\right) &{} \text { if } r \text { is even, }\\ &{}\\ \varOmega \left( \displaystyle \frac{r}{\log r}\log n\right) &{} \text { otherwise}. \end{array}\right. } \end{aligned}$$
(22)

Formula (22) improves on the bound \(t(\mathcal{H}^n_r, 1)=\varOmega (\log n)\) given in [5]. Remarkably, for \(\mathcal{H}^n_r\) our Theorem 3 recovers the result of [3] that \(t(\mathcal{H}^n_r, 1)=O(r \log n)\), for any \(r>2\).

On the other hand, using the equivalence between r-SCF matrices for \(\mathcal{H}^n_r\) and superimposed codes [27], and directly employing the non-existential bounds by [17, 33], we get that \(t(\mathcal{H}^n_r, r)=\varOmega \left( \frac{r^2}{\log r}\log n\right) \). In this case our Lemma 2 allows us to recover (asymptotically) the best known upper bounds [20] given by \(t(\mathcal{H}^n_r, r)=O(r^2 \log (n/r)).\)

Closing the gap in the above lower and upper bounds is equivalent to solve an outstanding combinatorial problem that has been open for decades. Recently, a solution was announced in [18], however this claim has now been retracted [19].

5 Conclusion

We have introduced the problem of k-strong conflict free multicoloring of hypergraphs. We have shown that it represents a common framework for many algorithmic and combinatorial problems that arise in a variety of areas. Despite its generality, we have been able to present significant results that, when instantiated on particular classes of graphs, either improve on previously known results or match the best known ones.

There are many interesting possible extensions of our findings. For instance, one could allow a small fraction of the hyperedges to be not correctly colorated, in the hope of further reducing the total number colors. Another possible relaxation of our problem arises when the requirement that a number of units rows must appear in some submatrices of a k-SCF matrix is substituted with the requirement that a number of rows with “few ones” appear. This is motivated by the advent of new technologies that allow successful transmission in wireless networks, despite a limited number of possible collision (e.g., see [16]).