4.2: Existencia de DEG
- Page ID
- 117112
En esta sección, sdr significa sdr completo. Es fácil ver que no todas las colecciones de conjuntos tienen un sdr. Por ejemplo,\[A_1=\{a,b\}, A_2=\{a,b\}, A_3=\{a,b\}.\nonumber\] El problema es claro: sólo hay dos representantes posibles, por lo que no se puede encontrar un conjunto de tres representantes distintos. Este ejemplo es un poco más general de lo que puede aparecer al principio. Considerar
\[A_1=\{a,b\}, A_2=\{a,b\}, A_3=\{a,b\}, A_4=\{b,c,d,e\}.\nonumber\]
Ahora el número total de posibles representantes es de 5, y solo necesitamos 4. Sin embargo, esto es imposible, porque los tres primeros conjuntos no tienen sdr considerados por ellos mismos. Por lo tanto, la siguiente condición, llamada Condición de Hall, es claramente necesaria para la existencia de una sdr: Para cada\(k\ge1\), y cada conjunto\(\{i_1,i_2,\ldots,i_k\}\subseteq [n]\),\(|\bigcup_{j=1}^k A_{i_j}|\ge k\). Es decir, el número de posibles representantes en cualquier colección de conjuntos debe ser al menos tan grande como el número de conjuntos. Ambos ejemplos no logran tener esta propiedad porque\(|A_1\cup A_2\cup A_3|=2< 3\).
Notablemente, esta condición es a la vez necesaria y suficiente.
Teorema \(\PageIndex{1}\): Hall's Theorem
Una colección de conjuntos\(A_1,A_2,\ldots,A_n\) tiene un sdr si y solo si por cada\(k\ge1\), y cada conjunto\(\{i_1,i_2,\ldots,i_k\}\subseteq [n]\),\(|\bigcup_{j=1}^k A_{i_j}|\ge k\).
- Prueba
-
Ya sabemos que el padecimiento es necesario, por lo que demostramos suficiencia por inducción en\(n\).
Supongamos\(n=1\); la condición es simplemente eso\(|A_1|\ge 1\). Si esto es cierto entonces no\(A_1\) está vacío y entonces hay un sdr. Esto establece el caso base.
Ahora supongamos que el teorema es cierto para una colección de\(k< n\) conjuntos, y supongamos que tenemos conjuntos que\(A_1,A_2,\ldots,A_n\) satisfacen la Condición de Hall. Tenemos que demostrar que hay un sdr.
Supongamos primero que para todos\(k< n\) y cada uno\(\{i_1,i_2,\ldots,i_k\}\subseteq [n]\), eso\(|\bigcup_{j=1}^k A_{i_j}|\ge k+1\), es decir, que estos sindicatos son más grandes de lo requerido. Elija cualquier elemento\(x_n\in A_n\) y defina\(B_i=A_i\backslash\{x_n\}\) para cada uno\(i< n\). Considera la colección de conjuntos\(B_1,\ldots,B_{n-1}\), y cualquier unión\(\bigcup_{j=1}^k B_{i_j}\) de una subcolección de los conjuntos. Hay dos posibilidades: cualquiera\(\bigcup_{j=1}^k B_{i_j}=\bigcup_{j=1}^k A_{i_j}\) o\(\bigcup_{j=1}^k B_{i_j}=\bigcup_{j=1}^k A_{i_j}\backslash\{x_n\}\), así que eso\(|\bigcup_{j=1}^k B_{i_j}|=|\bigcup_{j=1}^k A_{i_j}|\) o\(|\bigcup_{j=1}^k B_{i_j}|=|\bigcup_{j=1}^k A_{i_j}|-1\). En cualquier caso, ya que\(|\bigcup_{j=1}^k A_{i_j}|\ge k+1\),\(|\bigcup_{j=1}^k B_{i_j}|\ge k\). Así, por la hipótesis de inducción, la colección\(B_1,\ldots,B_{n-1}\) tiene un sdr\(\{x_1,x_2,\ldots,x_{n-1}\}\), y para cada\(i< n\),\(x_i\not= x_n\), por la definición de la\(B_i\). Así\(\{x_1,x_2,\ldots,x_{n}\}\) es un sdr para\(A_1,A_2,\ldots,A_n\).
Si no es cierto eso para todos\(k< n\) y cada uno\(\{i_1,i_2,\ldots,i_k\}\subseteq [n]\),\(|\bigcup_{j=1}^k A_{i_j}|\ge k+1\), entonces para algunos\(k< n\) y\(\{i_1,i_2,\ldots,i_k\}\),\(|\bigcup_{j=1}^k A_{i_j}|= k\). Sin pérdida de generalidad, podemos suponer eso\(|\bigcup_{j=1}^k A_{j}|= k\). Por la hipótesis de inducción,\(A_1,A_2,\ldots,A_k\) tiene un sdr,\(\{x_1,\ldots,x_k\}\).
Definir\(B_i=A_i\backslash \bigcup_{j=1}^k A_{j}\) para\(i> k\). Supongamos que\(\{x_{k+1},\ldots,x_{n}\}\) es un sdr para\(B_{k+1},\ldots,B_{n}\); entonces también es un sdr para\(A_{k+1},\ldots,A_{n}\). Además,\(\{x_1,\ldots,x_n\}\) es un sdr para\(A_{1},\ldots,A_{n}\). Así, para terminar la prueba basta con demostrar que\(B_{k+1},\ldots,B_{n}\) tiene un sdr. El número de sets aquí es\(n-k< n\), así que solo necesitamos demostrar que los conjuntos satisfacen la Condición de Hall.
Así que considera algunos conjuntos\(B_{i_1},B_{i_2},…,B_{i_l}\). Primero notamos que\[|A_1\cup A_2\cup\cdots\cup A_k\cup B_{i_1}\cup B_{i_2}\cup\cdots B_{i_l}|=k+|B_{i_1}\cup B_{i_2}\cup\cdots B_{i_l}|.\nonumber\] También\[|A_1\cup A_2\cup\cdots\cup A_k\cup B_{i_1}\cup B_{i_2}\cup\cdots B_{i_l}|=|A_1\cup A_2\cup\cdots\cup A_k\cup A_{i_1}\cup A_{i_2}\cup\cdots A_{i_l}|\nonumber\] y\[|A_1\cup A_2\cup\cdots\cup A_k\cup A_{i_1}\cup A_{i_2}\cup\cdots A_{i_l}|\ge k+l.\nonumber\] Armando estos da\[\eqalign{ k+|B_{i_1}\cup B_{i_2}\cup\cdots\cup B_{i_l}|&\ge k+l\cr |B_{i_1}\cup B_{i_2}\cup\cdots\cup B_{i_l}|&\ge l\cr. }\nonumber\] Así,\(B_{k+1},\ldots,B_{n}\) tiene un sdr, que termina la prueba.