# Are there mathematical (combinatorial) objects to represent such set systems?

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.

• 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$. – dtldarek Nov 8 '13 at 13:26
• 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$. – Simon Markett Nov 8 '13 at 13:30
• @dtldarek Yes, the non-intersect property is necessary. I have added it. Thx. – hengxin Nov 8 '13 at 13:42
• @SimonMarkett They ($S_{ij}'$) are distinct and $n \ge k$. I have modified it. Thx. – hengxin Nov 8 '13 at 13:44
• 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$? – Simon Markett Nov 8 '13 at 14:03

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.
• 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. – hengxin Nov 14 '13 at 10:03