Productos cartesianos representados como uniones disjuntas

Question

Supongamos que $k$ conjuntos finitos $S_1, \ldots, S_k$ y su producto cartesiano $S = S_1 \times \ldots \times S_k$ .

Supongamos que elimino $n$ elementos (distintos) de $S$ y llamemos a ese conjunto más pequeño $S'$ . Me interesa representar a $S'$ como unión de distinto Productos cartesianos.

¿Existe un límite superior, en términos de $k$ y $n$ ¿sobre el número de productos distintos que puedo necesitar en una unión de este tipo?

Un ejemplo sencillo $S_1 = \{ a, b, c \}$ , $S_2 = \{ 1, 2, 3 \}$ , $S = S_1 \times S_2$ .

Si tomo $S' = S \setminus \{ (b, 2), (b, 3) \}$ puedo escribirlo como $S' = \left( \{ a, c \} \times \{ 1, 2, 3 \} \right) \cup \left(\{ b \} \times \{ 1 \} \right) $ . En este caso, he utilizado dos productos. Si hubiera eliminado $(c,3)$ en lugar de $(b,3)$ Creo que habría necesitado al menos tres.

(La razón por la que pido un límite en términos de $k$ y $n$ es que una simple interpretación geométrica me hace creer que los tamaños de los conjuntos $S_i$ son irrelevantes, aunque pueden entrar en juego cuando el número de elementos eliminados se aproxime al tamaño de $S$ . Por favor, corríjanme si me equivoco).

Answer 1

Dejemos que los elementos que eliminamos se denoten por $s^j=(s_1^j,s_2^j,\ldots,s_k^j)$ para $j=1,2,\ldots,n$ . Nos interesa el conjunto $$(S_1\times S_2\times\ldots\times S_k)\setminus\{s^1,s^2,\ldots,s^n\}.$$

Reclamación. Un límite superior (posiblemente muy burdo) viene dado por $\frac{n^k-1}{n-1}$ .

Prueba. Lo demostraremos por inducción en $k$ .

Para $k=1$ no hay ningún problema. El conjunto $S_1\setminus\{s^1,s^2,\ldots,s^n\}$ es un producto cartesiano con un factor, así que hemos terminado: el límite superior es $1$ en este caso.

Para $k\to k+1$ Obsérvese que podemos reescribir el conjunto de la siguiente manera: $$\begin{align}&(S_1\times S_2\times\ldots\times S_{k+1})\setminus\{s^1,s^2,\ldots,s^n\}=\\&=(S_1\times S_2\times\ldots\times S_{k+1})\setminus\{s^1,s^2,\ldots,s^n\}\\&=\bigcup_{x\in S_{k+1}}(S_1\times S_2\times\ldots\times S_k\times\{x\})\setminus\{s^1,s^2,\ldots,s^n\}\\&=\left(\bigcup_{j=1}^n(S_1\times S_2\times\ldots\times S_k\times\{s_{k+1}^j\})\setminus\{s^1,s^2,\ldots,s^n\}\right)\cup(S_1\times S_2\times\ldots\times (S_{k+1}\setminus\{s_{k+1}^1,\ldots,s_{k+1}^n\})),\end{align}$$ que es (si omitimos los conjuntos que aparecen más de una vez en la primera unión) una unión disjunta de como máximo $n$ conjuntos de la forma $$(S_1\times S_2\times\ldots\times S_k\times\{s_{k+1}^j\})\setminus\{s^1,s^2,\ldots,s^n\},$$ y un único producto cartesiano de $k+1$ conjuntos. Por la hipótesis de inducción, cada conjunto $$(S_1\times S_2\times\ldots\times S_k\times\{s_{k+1}^j\})\setminus\{s^1,s^2,\ldots,s^n\}$$ puede escribirse como una unión disjunta de como máximo $\frac{n^k-1}{n-1}$ Productos cartesianos. Por lo tanto, nuestro conjunto puede escribirse como una unión disjunta de como máximo $n\frac{n^k-1}{n-1}+1 = \frac{n^{k+1}-1}{n-1}$ Productos cartesianos (con $k+1$ factores cada uno, por supuesto). $\square$

Hay que tener en cuenta que para encontrar mejores límites podrían ser necesarios métodos combinatorios más sofisticados.