Family of sets with unique subsets I am given a set $M\subseteq\{1,\dots,n\},\,|M|=m$ and a famliy of $k$-sets ($k<m$) $\mathcal{U}=\{U_1,\dots,U_p\},\,U_{i}\subset M$. For this family, I would like to check one of the following conditions:
strong each $U_i$ contains a $(k-1)$ subset $D_i$, which is not a subset of all other $U_j$ ($D_i\subset U_{j}\,\Leftrightarrow\,i=j$)
weak there is an ordering of the sets in $\mathcal{U}$ such that, after relabeling, each $U_{i}$ contains a $(k-1)$ subset $D_i$ which is not in the remaining $U_{j}$ ($D_i\subset U_i$ and $D_i \nsubseteq U_j,\, j>i$)
My question: Did this problem already appear in some paper or even textbook and is there a way to attack it? Just speaking about the sets doesn't seem to give enough structure, so I would like to put it into another context (e.g. graphs, simplicial complexes etc.).
in the particular case I am thinking about: $n$ is odd and $k=\frac{n-1}{2}$ and $m=k+j$, $j$ even.
 A: This is more a collection of observations and relevant definitions than an answer.
First, you can take $M = [m] = \{1, \ldots, m \}$ and forget about $n$.
For a family of $k$-sets $\mathcal A$, the shadow of $\mathcal A$ is $\partial \mathcal A = \{B \in [m]^{(k-1)} : B \subset A \text{ for some } A \in \mathcal A\}$, where $[m]^{(k-1)}$ is the set of $(k-1)$-subsets of $[m]$.  There is a natural bipartite graph structure on $(\mathcal A, \partial \mathcal A)$; for the strong condition you want to find vertices in $\partial \mathcal A$ of degree 1, one from the neighbourhood of each vertex in $\mathcal A$.  I don't think this is a standard problem, possibly because it's so easy to check for any given instance.
For the weak condition you can build the graph as before, then take vertices in $\partial \mathcal A$ of degree 1 greedily, deleting the neighbour in $\mathcal A$ each time.  If you get stuck then there is no good choice of $D_i$, as removing sets never makes the conditions for the remaining sets harder to satisfy.
Both of these algorithms take time only polynomial in $k$ and $|\mathcal A|$.
