We are given a set of elements $U$ and $n$ binary functions, i.e. $f_i: U \to \{0,1\}$. Moreover, each function maps exactly $k$ elements of $U$ to 1. The task is to create a collection of $n$ disjoint sets $S_i$ satisfying the following property: $$ \forall S_i\ \forall j \ne i\ \exists e \in S_i: f_j(e) = 1$$ The question is what is the minimum $k$ so that the above construction is possible.
My work so far: let $g(n)$ denote the minimum $k$. Clearly, $g(n) \ge n-1$. However, if $g(n) = n-1$ but every $f_i$ maps the same subset of $U$ to 1 the construction is not possible. Thus $g(n) \ge n$. I also have an upper bound, $g(n) \le (n-1)^2$. Consider the following algorithm: in round $i$, if $S_j$ does not include an element $f_i$ maps to 1 we add one such element to $S_j$. Before round $n$ begins, we have $$\left\lvert\bigcup_i S_i\right\rvert = (n-1)\cdot (n-2) + (n-1) = (n-1)^2$$ thus if $g(n) \ge (n-1)^2$ the assignment is possible.
Observations
- $g(2) = 2$ and $g(3) = 3$. I can provide proofs if needed. Also it gets annoyingly more complex to compute $g(4)$.
- For every $e \in U$ we can see the vector $f_1(e), \dots, f_n(e)$ as a $n$-bit binary label, hence my title
- We can reduce $U$ to $U'$ such that $U'$ contains only elements that at least one function maps to 1
My intuition is that there is some connection between my problem and some (multi)graph edge coloring problem or bipartite coloring but I am not sure exactly what I am looking for. Any ideas?
Edit: I found a different formulation and think it may be helpful to include it.
Assume for now that we strengthen the needed property to $$ \forall S_i\ \forall j\ \exists e \in S_i: f_j(e) = 1$$
Consider the universe of elements $U = \{1,\dots,n\}$ and a collection of $m$ subsets of $U$ such that each $i \in U$ appears at exactly $k$ of the $m$ sets. What is the least $k$ so that we can create $n$ non overlapping set covers of $U$, i.e. no two set covers share a subset.
To return to my original question let me define the "almost set cover" $C_i$ as the set cover of $U\setminus i$. Then the question is what is the least $k$ so that we can create all the almost set covers without overlap. (Edit 3: based on the set cover formulation I also asked the question here)
Edit 2: A refinement of the upper bound is achievable via the pigeonhole principle. Before round $n$ begins, there are $n-1$ nests of size $n-2$ and 1 nest of size $n-1$. Thus if $g(n) \ge (n-2)^2 + n-1 + 1 = n^2 - 3n + 4$ the construction is once again possible. Also, this hints at a way to improve the upper bound a bit more: for instance if $g(n) = n^2 - 3n + 3$ we can only fail by one element in the last round. That can only occur when there are two elements $e, e'$ assigned in $S_i$ and $S_n$ respectively at round $t$ such that $f_t(e) = f_t(e') = 1$ and $f_n(e) =0, f_n(e')=1$. Then we can simply swap them and we lowered the bound by 1.