¿Hay objetos matemáticos (combinatorios) para representar a dichos sistemas de ajuste?

Question

Antecedentes:

Este es un problema que surge a partir de mi estudio en ciencias de la computación. En su apariencia, que consiste en establecer sistemas.

Un conjunto de sistema de $\mathcal{S} = \{S_1, S_2, \ldots, S_m \}$ es una colección de subconjuntos de a $S_i \subseteq U$ de un universo finito $U$.
Un quórum sistema es un conjunto de sistema de $\mathcal{QS}$ que tiene la intersección de la propiedad: $\forall S_i, S_j \in \mathcal{QS}, S_i \cap S_j \neq \emptyset$.

Por ejemplo, si $|U| = n$ (n es impar), todos los subconjuntos de cardinalidad estrictamente mayor que $\frac{n}{2}$ construir un quórum del sistema.

Mi problema es el siguiente:

Ahora, dado un quórum de sistema de $\mathcal{QS}$ (sobre el universo $U$) y una constante de $k$, cómo construir un sistema de conjunto $\mathcal{S'} = \{ S_1', S_2', \ldots, S_n' \}$ ($n \ge k$, también en el universo $U$) tal que: la unión de cualquier exacto $k$ distintos subconjuntos de a $\mathcal{S'}$ intersecta a cualquier subconjunto de a $\mathcal{QS}$. Formalmente,

1. el $k$-se cruzan propiedad: $\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$; y
2. el $k-1$-nonintersect propiedad: $\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$?

He comprobado que algunos matemáticos libros (especialmente en la combinatoria) pero no pudo encontrar estrechamente relacionados con los objetos matemáticos. Entonces, ¿podría usted me ofrecen algunas sugerencias, consejos o referencias?

EDIT: he añadido el set-theory etiqueta porque he encontrado extremal la teoría de conjuntos puede ser útil.

Answer 1

Es probable que los cuantificadores en relación con el conjunto de sistema de $\mathcal{S}'$ a del quórum de sistema de $\mathcal{QS}$ han declarado incorrectamente. Como está indicado, si $k \gt 1$ se requiere que cada $S_i \in \mathcal{QS}$ tanto para intersecar y evitar la intersección de cada una de las $S_j' \in \mathcal{S}'$.

En detalle, corregir algunos $S_i \in \mathcal{QS}$. Desde $n \ge k$, podemos incluir cualquier $S_j' \in \mathcal{S}'$ en una colección de $\mathscr{C}$ $k$ conjuntos distintos de $\mathcal{S}'$, y por (1) la unión a lo largo de esta $k$-colección cruza $S_i$. Pero por (2), si soltamos $S_j'$ $\mathscr{C}$ y obtiene la colección de exactamente $k-1$ conjuntos de $\mathscr{C} \backslash \{S_j'\}$, su unión evita la intersección $S_i$. De ello se desprende que la intersección de a $\cup \mathscr{C}$ $S_i$ $S_j'$ tienen intersección no vacía con $S_i$ (debido a la intersección, se hace vacío al $S_j'$ es eliminado de $\mathscr{C}$).

Por otro lado también podemos probar a $S_j' \cap S_i$ está vacía! Es decir, si se omite la de $\mathscr{C}$ un conjunto de otros de $S_j'$ (aquí se utiliza el supuesto de $k \gt 1$), llegamos a otro de la unión de $k-1$ pone en $\mathcal{S}'$ que evita la intersección $S_i$. Pero ahora $S_j'$ está incluido en esa unión, por lo $S_j' \cap S_i = \emptyset$.

Tomando un paso atrás de estas condiciones, me parece probable que el problema radica en cómo la $k-1$ nonintersect propiedad está escrita. Observe que si $k \gt 1$ y arbitrario de la unión de $k-1$ conjuntos de $\mathcal{S}'$ que se requiere para ser distinto de todos los $S_i \in \mathcal{QS}$, entonces la unión de todos los conjuntos en $\mathcal{S}'$ debe ser distinto a partir de la unión de todos los conjuntos en $\mathcal{QS}$.

Mi sugerencia sería la de considerar una versión debilitada de (2) en la que sólo algunos $S_i \in \mathcal{QS}$, dependiendo de la elección de $k-1$ conjuntos de $\mathcal{S}'$ tomado, es disjunta de la unión de este último.