Hanging a painting with nails so that removing any subset of nails from a given collection makes painting fall, and subsets are minimal

98 Views Asked by At

So I'm aware of the result that for positive integers $k \leq n$ it's possible to hang a painting with $n$ nails, such that if any $k$ nails are removed then the painting falls, but never when $k-1$ nails are removed. However I'm interested in generalizing to arbitrary minimal subsets of nails removed that cause the painting to fall when one of the subsets of nails is removed. Suppose we have a collection $C$ of subsets of integers between 1 and $n$. Under what conditions do the subsets of $C$ satisfy that we can hang the painting so that, if any subset $S \in C$ of nails is removed then the painting falls, and each subset $S$ is minimal with respect to this property (i.e. no proper subset of $S$ causes the painting to fall), and there are no $S \notin C$ necessarily "implied" minimal subsets $S$ (implied by the existing subsets in $C$) that cause the painting to fall?

Also, for such a collection $C$, how do we construct (say, algebraically) a reasonably short (preferably shortest) sequence of passing the string to the left or right over nails to make the minimal subsets of nails removed that cause the painting to fall are exactly the $S \in C$?

1

There are 1 best solutions below

0
On

As joriki mentioned:

It seems that this paper answers most of your questions? arxiv.org/abs/1203.3602

The paper is quite comprehensive about many variants of this question.