2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Err.. Maybe a generalization of Sperner's Theorem would give you a hint in how to start this? They're not immediately related, but maybe some of the same techniques used in the proof would help you. See en.wikipedia.org/wiki/Sperner%27s_theorem for examples. $\endgroup$
    – Gwyn Whieldon
    Mar 11, 2014 at 12:59
  • $\begingroup$ What does $n$ have to do with it? $\endgroup$
    – Noah Stein
    Mar 11, 2014 at 13:15
  • $\begingroup$ For the problem, nothing really. It comes from the context I am thinking about. $\endgroup$
    – Richard
    Mar 11, 2014 at 13:21

1 Answer 1

Reset to default
2
$\begingroup$

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|$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for your answer. Do you have a reference for this? $\endgroup$
    – Richard
    Mar 11, 2014 at 13:21
  • $\begingroup$ Definitions and basic properties of shadows should appear in any textbook or lecture notes on extremal set theory. Everything else was just unpacking definitions to expose the underlying combinatorial problem, so there aren't any references as such. $\endgroup$
    – Ben Barber
    Mar 11, 2014 at 13:28
  • $\begingroup$ For that matter M and m are also dispensable: union of the U_i is not. $\endgroup$
    – The Masked Avenger
    Mar 11, 2014 at 14:20
  • 1
    $\begingroup$ Also, it should be polynomial in kA, unless your algorithm does not unpack a set or do the moral equivalent of unpacking. $\endgroup$
    – The Masked Avenger
    Mar 11, 2014 at 15:13
  • $\begingroup$ @TheMaskedAvenger Thanks, I've edited that in. $\endgroup$
    – Ben Barber
    Mar 11, 2014 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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