5
$\begingroup$

Background:

This is a problem arising from my study on computer science. In its appearance, it involves set systems.

A set system $\mathcal{S} = \{S_1, S_2, \ldots, S_m \}$ is a collection of subsets $S_i \subseteq U$ of a finite universe $U$.
A quorum system is a set system $\mathcal{QS}$ that has the intersection property: $\forall S_i, S_j \in \mathcal{QS}, S_i \cap S_j \neq \emptyset$.

For example, if $|U| = n$ (n is even), all the subsets with cardinality strictly greater than $\frac{n}{2}$ construct a quorum system.

My problem is as follows:

Now given a quorum system $\mathcal{QS}$ (on universe $U$) and a constant $k$, how to construct a set system $\mathcal{S'} = \{ S_1', S_2', \ldots, S_n' \}$ ($n \ge k$, also on universe $U$) such that: the union of any exact $k$ distinct subsets of $\mathcal{S'}$ intersects any single subset of $\mathcal{QS}$. Formally,

  1. the $k$-intersect property: $\forall S_{i1}', S_{i2}', \ldots, S_{ik}' \in \mathcal{S'}, S_i \in \mathcal{QS}, (S_{i1}' \bigcup S_{i2}' \bigcup \ldots \bigcup S_{ik}') \bigcap S_i \neq \emptyset$; and
  2. the $k-1$-nonintersect property: $\forall S_{i1}', S_{i2}', \ldots, S_{ik-1}' \in \mathcal{S'}, S_i \in \mathcal{QS}, (S_{i1}' \bigcup S_{i2}' \bigcup \ldots \bigcup S_{ik-1}') \bigcap S_i = \emptyset$?

I checked some mathematical books (especially in combinatorics) but failed to find closely related mathematical objects. So could you offer me some suggestions, hints, or references?

EDIT: I added the set-theory tag because I found extremal set theory maybe helpful.

$\endgroup$
  • $\begingroup$ Do you want some additional properties, like there are collections of $k-1$ subsets that do not intersect with some $S_i$? Because in current wording setting $\mathcal{S}' = \mathcal{QS}$ would fit your definition given $k \geq 1$. $\endgroup$ – dtldarek Nov 8 '13 at 13:26
  • $\begingroup$ Do you allow any of the $S_{ij}'$ to coincide? If that's the case, you would also allow for all of them to be the same, and therefore necessarily need $\forall S_i'\in S', \forall S_j\in QS: S_i'\cap S_j\neq\emptyset$. If you require all of them to be distinct you need something like $n\geq k$. $\endgroup$ – Simon Markett Nov 8 '13 at 13:30
  • $\begingroup$ @dtldarek Yes, the non-intersect property is necessary. I have added it. Thx. $\endgroup$ – hengxin Nov 8 '13 at 13:42
  • $\begingroup$ @SimonMarkett They ($S_{ij}'$) are distinct and $n \ge k$. I have modified it. Thx. $\endgroup$ – hengxin Nov 8 '13 at 13:44
  • $\begingroup$ I think the $k-1$-property is still not entirely precise. Do you want: For any $S_i\in QS$ there exist $k-1$ sets in $S'$ such that their union doesn't intersect $S_i$? $\endgroup$ – Simon Markett Nov 8 '13 at 14:03
1
$\begingroup$

It is likely that the quantifiers in relating the set system $\mathcal{S}'$ to quorum system $\mathcal{QS}$ have been stated incorrectly. As presently stated, if $k \gt 1$ we require each $S_i \in \mathcal{QS}$ both to intersect and avoid intersecting each $S_j' \in \mathcal{S}'$.

In detail, fix some $S_i \in \mathcal{QS}$. Since $n \ge k$, we can include any $S_j' \in \mathcal{S}'$ in a collection $\mathscr{C}$ of $k$ distinct sets from $\mathcal{S}'$, and by (1) the union over this $k$-collection intersects $S_i$. But by (2), if we drop $S_j'$ from $\mathscr{C}$ and get the collection of exactly $k-1$ sets $\mathscr{C} \backslash \{S_j'\}$, their union avoids intersecting $S_i$. It follows that the intersection of $\cup \mathscr{C}$ with $S_i$ is due to $S_j'$ having nonempty intersection with $S_i$ (because the intersection becomes empty when $S_j'$ is removed from $\mathscr{C}$).

On the other hand we can also prove $S_j' \cap S_i$ is empty! That is, if we omit from $\mathscr{C}$ a set other than $S_j'$ (here we use the assumption $k \gt 1$), we get another union of $k-1$ sets in $\mathcal{S}'$ which avoids intersecting $S_i$. But now $S_j'$ is included in that union, so $S_j' \cap S_i = \emptyset$.

Taking a step back from these conditions, it seems to me likely that the problem lies in how the $k-1$ nonintersect property is phrased. Notice that if $k \gt 1$ and an arbitrary union of $k-1$ sets from $\mathcal{S}'$ is required to be disjoint from every $S_i \in \mathcal{QS}$, then the union of all sets in $\mathcal{S}'$ must be disjoint from the union of all sets in $\mathcal{QS}$.

My suggestion would be to consider a weakened version of (2) in which only some $S_i \in \mathcal{QS}$, depending on the choice of $k-1$ sets from $\mathcal{S}'$ taken, is disjoint from the union of the latter.

$\endgroup$
  • $\begingroup$ Thanks for your analysis. I have realized that both $k$-intersect property and $k-1$-nonintersect property cannot be simultaneously satisfied. I have to go back to the original computer science problem and try to reformulate its mathematical part. $\endgroup$ – hengxin Nov 14 '13 at 10:03

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.