2
$\begingroup$

I have a combinatorics problem and I am asking for a solution or a reference in order to solve it.

Since the problem is rather long, I will translate it mathematically.

Suppose I have a $n \times m$ matrix with no entries.

I want to fill the matrix with entries equal to $0$ or $1$, subject to some conditions.

We define a sum operation, which I denote by $\vee$, which is the or operation (attention: not XOR / $\oplus$ / addition modulo $2$ / exclusive-or operation): \begin{array}{c|c|c|c|} \vee& 0 & 1 \\ \hline 0 & 0 & 1 \\ \hline 1 & 1 & 1 \\ \hline \end{array} We will use the same symbol $\vee$ to sum rows of a matrix component by component. The result is thus a row vector.

Let $t \in \{1,\ldots,n\}$.

Condition 1: For each subset $S \subseteq \{1,\ldots,n\}$ of cardinal $t$, the sum of the $S$-rows is equal to $(1,\ldots,1)$.

Condition 2: For each subset $S \subseteq \{1,\ldots,n\}$ of cardinal $t-1$, the sum of the $S$-rows is not equal to $(1,\ldots,1)$.

Trivial consequence: Each column has to have at least $t$ ones.

And that's it! Brute-force is not an option, since in worst-case it would take $\binom{n}{t}^m$ attempts. If, for example, $t=\frac{n}{2}$, brute-force is exponential-time. I am looking for a polynomial-time algorithm. On the other hand, I could simply randomly generate a matrix with entries equal to $0$ or $1$ and check the conditions. But again, by the same reason, checking the conditions would be exponential-time.

Thanks in advance.

$\endgroup$
  • $\begingroup$ This is equivalent to placing several locks on a treasure chest and distributing copies of the keys various subsets of $n$ pirates so that any $t$ pirates can open the chest, but any $t-1$ cannot. This is also discussed here. $\endgroup$ – Mike Earnest Feb 7 at 20:29
2
$\begingroup$

Let $M$ be your matrix.
For each $S \subset \{1,\ldots,n\}$, let $Z(S) = \{j \in \{1,\ldots,m\}: \sum_{i \in S} M_{ij} = 0\}$. The condition says $Z(S)$ is nonempty if $|S|=t-1$, but empty if $|S|=t$. In particular, for any distinct $S_1, S_2$ with $|S_1| = |S_2| = t-1$, $Z(S_1)$ and $Z(S_2)$ are disjoint. Thus we need $m \ge {n \choose t-1}$.

Conversely, if $m \ge {n \choose t-1}$ we can construct such an $M$. For simplicity, suppose $m={n \choose t-1}$ (we can always add more columns of all $1$'s). Namely, let $S_1, \ldots, S_{m}$ be an enumeration of the subsets of $\{1,\ldots,n\}$ of cardinality $t-1$, and define $M_{ij} = 0$ if $i \in S_{j}$, $1$ otherwise.

$\endgroup$
  • $\begingroup$ Thank you for answering. I don't understand the statement ''In particular, (...), $Z(S_1)$ and $Z(S_2)$ are disjoint." This is not clear and it seems false... $\endgroup$ – Leafar Feb 7 at 19:08
  • $\begingroup$ Let $S_3$ be the union of $S_1$ and one element of $S_2$ that is not in $S_1$. Then $|S_3| = t$. If $j \in Z(S_1) \cap Z(S_2)$, then $j \in Z(S_3)$, which is impossible. $\endgroup$ – Robert Israel Feb 7 at 20:02
  • $\begingroup$ Ok, I agree. Now I have another question... Is this matrix unique, up to the order of the subsets and having an arbitrary number of columns of all 1's? From your answer it seems so... $\endgroup$ – Leafar Feb 8 at 8:18
1
$\begingroup$

This is very similar to Robert Israel's answer, but reworded.

For each subset $S$ of size $t-1$, there must be at least one column, $c$, where all the entries in $c$ whose row is in $S$ are $0$. Furthermore, all the other entries in $c$ must be $1$, since for every superset $S'$ of $S$ of size $t$, there is at least one $1$ in some row in $S'$ in $c$, and it cannot occur in $S$.

Therefore, for each of the $\binom{n}{t-1}$ possibilities for $S$, a particular column must exist; one with zeroes in $S$ and ones elsewhere. This means there must be at least $\binom{n}{t-1}$ columns. In particular, a simple algorithm to construct the matrix is this; list all of the subsets of $S$, and for each one, add a column to the matrix which is zero for the rows in $S$ and one elsewhere. Then pad the matrix to $m$ columns by adding columns of ones.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.