4.3: DEG parciales
- Page ID
- 117115
En esta sección, sdr significa sdr parcial.
Si no hay sdr completo, naturalmente queremos saber cuántos de los\(n\) conjuntos se pueden representar, es decir, cuál es el mayor valor de\(m\) para que algunos\(m\) de los conjuntos tengan un sdr completo. Como no hay sdr completo, hay conjuntos\(A_{i_1},A_{i_2},\ldots,A_{i_k}\) tales que\(|\bigcup_{j=1}^k A_{i_j}|=l< k\). Claramente, en\(l\) la mayoría de estos\(k\) juegos tienen un sdr completo, por lo que ningún sdr para\(A_1,A_2,\ldots,A_n\) puede ser mayor que\(n-k+l\). Así, no\(m\) puede ser mayor que el valor mínimo, sobre todas\(k\) y todas las colecciones de conjuntos\(A_{i_1},A_{i_2},\ldots,A_{i_k}\), de\(n-k+|\bigcup_{j=1}^k A_{i_j}|\). Tenga en cuenta que si\(|\bigcup_{j=1}^k A_{i_j}|>k\)\(n-k+|\bigcup_{j=1}^k A_{i_j}|>n\),, que no nos dice nada. Si\(k=0\),\(n-k+|\bigcup_{j=1}^k A_{i_j}|=n\) (porque los sindicatos vacíos están vacíos), así se nos garantiza que el mínimo nunca es mayor que\(n\). De hecho, el valor mínimo de la expresión es exactamente el tamaño de un sdr más grande.
Teorema \(\PageIndex{1}\)
El tamaño máximo de un sdr para los conjuntos\(A_1,A_2,\ldots,A_n\) es el valor mínimo, para\(0\le k\le n\) y conjuntos\(A_{i_1},A_{i_2},\ldots,A_{i_k}\), de\(n-k+|\bigcup_{j=1}^k A_{i_j}|\).
- Prueba
-
Dado que ningún sdr puede ser mayor que este valor mínimo, basta con mostrar que podemos encontrar un sdr cuyo tamaño sea este mínimo. La prueba es por inducción\(n\); el caso\(n=1\) es fácil.
Supongamos primero que el valor mínimo es\(n\), para que para todas\(k\) y todas las colecciones de conjuntos\(A_{i_1},A_{i_2},\ldots,A_{i_k}\),\[n-k+|\bigcup_{j=1}^k A_{i_j}|\ge n.\nonumber\] luego reordenando veamos que
\[|\bigcup_{j=1}^k A_{i_j}|\ge k,\nonumber\]
así que por el Teorema de Hall (4.2.1), hay una sdr de tamaño\(n\).
Tenga en cuenta que el valor mínimo de\(n-k+|\bigcup_{j=1}^k A_{i_j}|\) ocurre cuando\(|\bigcup_{j=1}^k A_{i_j}|-k\) es un mínimo, es decir\[\min(n-k+|\bigcup_{j=1}^k A_{i_j}|)= n+\min(|\bigcup_{j=1}^k A_{i_j}|-k).\nonumber\] Supongamos ahora que el mínimo\(m\) es menor que\(n\), y que\(m=n-k+|\bigcup_{j=1}^k A_{i_j}|\), con\(0< k< n\). Dejar\(B_j=A_{i_j}\); ya que\(k< n\), la hipótesis de inducción se aplica a los conjuntos\(B_1,\ldots,B_k\). Ya que cada conjunto\(B_j\) es\(A_{i_j}\),\(|\bigcup_{j=1}^l B_{h_j}|-l\ge |\bigcup_{j=1}^k A_{i_j}|-k\), para todos\(l\) y\(B_{h_1},\ldots,B_{h_l}\). Así, el valor mínimo de\(|\bigcup_{j=1}^l B_{i_j}|-l\), sobre todo\(l\) y\(B_{h_1},\ldots,B_{h_l}\), es\(|\bigcup_{j=1}^k B_{j}|-k=|\bigcup_{j=1}^k A_{i_j}|-k\), así por la hipótesis de inducción, los conjuntos\(A_{i_1},A_{i_2},\ldots,A_{i_k}\) tienen una sdr de tamaño\(k-k+|\bigcup_{j=1}^k A_{i_j}|=|\bigcup_{j=1}^k A_{i_j}|=m-n+k\),\(\{x_1,\ldots,x_{m-n+k}\}\).
Ahora considere los\(n-k\) conjuntos que consisten en esos conjuntos originales que no están en\(A_{i_1},A_{i_2},\ldots,A_{i_k}\), es decir,\(\{A_i\mid i\notin\{i_1,\ldots,i_k\}\}\). Que\(C_i=A_i\backslash \bigcup_{j=1}^k A_{i_j}\)\(i\) no entre\(i_1,i_2,\ldots,i_k\). Considera algunos conjuntos\(C_{g_1},C_{g_2},\ldots,C_{g_l}\). Si\(|\bigcup_{j=1}^l C_{g_j}|< l\) entonces\(|\bigcup_{j=1}^l C_{g_j}|-l< 0\) y\[\eqalign{ n-k+|\bigcup_{j=1}^k A_{i_j}| &> n-k-l+|\bigcup_{j=1}^l C_{g_j}|+|\bigcup_{j=1}^k A_{i_j}|\cr &\ge n-(k+l)+|C_{g_1}\cup\cdots\cup C_{g_l}\cup A_{i_1}\cup\cdots \cup A_{i_k}|\cr &= n-(k+l)+|A_{g_1}\cup\cdots\cup A_{g_l}\cup A_{i_1}\cup\cdots \cup A_{i_k}|,\cr }\nonumber\] contradiciendo el hecho de que\(n-k+|\bigcup_{j=1}^k A_{i_j}|\) es un mínimo. Así, por el Teorema de Hall (4.2.1), los conjuntos\(C_{g_1},C_{g_2},\ldots,C_{g_{n-k}}\) tienen un sdr completo\(\{y_1,\ldots,y_{n-k}\}\). Por la definición de los conjuntos\(C_i\),\(\{x_1,\ldots,x_{m-n+k}\}\cap\{y_1,\ldots,y_{n-k}\}=\emptyset\), así\(\{x_1,\ldots,x_{m-n+k}\}\cup \{y_1,\ldots,y_{n-k}\}\) es una sdr de tamaño\(m-n+k+n-k=m\) como se desee.
Por último, supongamos que el valor mínimo de\(n-k+|\bigcup_{j=1}^k A_{i_j}|\) ocurre sólo cuando\(k=n\), así queremos un sdr de tamaño\[ n-n+|\bigcup_{j=1}^n A_{j}|=|\bigcup_{j=1}^n A_{j}|.\nonumber\] Then\[\eqalign{ n-(n-1)+|\bigcup_{j=1}^{n-1} A_{j}|&>|\bigcup_{j=1}^n A_{j}|\cr 1+|\bigcup_{j=1}^{n-1} A_{j}|&>|\bigcup_{j=1}^n A_{j}|\cr |\bigcup_{j=1}^{n-1} A_{j}|&\ge|\bigcup_{j=1}^n A_{j}|.\cr }\nonumber\] Since\(|\bigcup_{j=1}^{n-1} A_{j}|\le|\bigcup_{j=1}^n A_{j}|\),\(|\bigcup_{j=1}^{n-1} A_{j}|=|\bigcup_{j=1}^n A_{j}|\). Por la hipótesis de inducción, el teorema se aplica a los conjuntos\(A_1,A_2,\ldots,A_{n-1}\). Si el mínimo de\((n-1)-l+|\bigcup_{j=1}^l A_{i_j}|\) ocurre cuando\(l=n-1\), entonces hay una sdr de tamaño\((n-1)-(n-1)+|\bigcup_{j=1}^{n-1} A_{j}| =|\bigcup_{j=1}^{n-1} A_{j}| =|\bigcup_{j=1}^{n} A_{j}|\), según se desee.
Si el mínimo ocurre cuando\(l< n-1\) y no cuando\(l=n-1\), entonces\[\eqalign{ (n-1)-l+|\bigcup_{j=1}^{l} A_{i_j}|< |\bigcup_{j=1}^{n-1} A_{j}|\cr n-l+|\bigcup_{j=1}^{l} A_{i_j}|< |\bigcup_{j=1}^{n-1} A_{j}|+1\cr }\nonumber\] y por suposición\[ n-l+|\bigcup_{j=1}^{l} A_{i_j}|>|\bigcup_{j=1}^{n} A_{j}|.\nonumber\] Así\[\eqalign{ |\bigcup_{j=1}^{n} A_{j}|&< n-l+|\bigcup_{j=1}^{l} A_{i_j}|\cr &< |\bigcup_{j=1}^{n-1} A_{j}|+1\cr &=|\bigcup_{j=1}^{n} A_{j}|+1.\cr }\nonumber\] Esto significa que hay un entero estrictamente entre dos enteros consecutivos, una contradicción. Esto completa la prueba.
Si bien este teorema proporciona un método para calcular el tamaño de un sdr máximo, el método apenas es eficiente: requiere mirar todas las colecciones posibles de los conjuntos. Tampoco proporciona una manera de encontrar un sdr real, es decir, los representantes reales. Vamos a solucionar estos problemas en las dos últimas secciones de este capítulo.