# Cartesian products represented as disjoint unions

Assume $k$ finite sets $S_1, \ldots, S_k$ and their Cartesian product $S = S_1 \times \ldots \times S_k$.

Suppose I remove $n$ (distinct) elements from $S$, and let us call that smaller set $S'$. I am interested in representing $S'$ as a union of distinct Cartesian products.

Is there an upper bound, in terms of $k$ and $n$, on the numbers of distinct products I may need in such a union?

As a simple example, consider $S_1 = \{ a, b, c \}$, $S_2 = \{ 1, 2, 3 \}$, $S = S_1 \times S_2$.

If I take $S' = S \setminus \{ (b, 2), (b, 3) \}$, I can write it as $S' = \left( \{ a, c \} \times \{ 1, 2, 3 \} \right) \cup \left(\{ b \} \times \{ 1 \} \right)$. In this case, I used two products. Had I removed $(c,3)$ instead of $(b,3)$, I believe I would have needed at least three.

(The reason I am asking for a bound in terms of $k$ and $n$ is that a simple geometric interpretation makes me believe the sizes of the sets $S_i$ are irrelevant — though they may come into play when the number of removed elements approaches the size of $S$. Please correct me if I am wrong.)

-

Let the elements we remove be denoted by $s^j=(s_1^j,s_2^j,\ldots,s_k^j)$ for $j=1,2,\ldots,n$. We are interested in the set $$(S_1\times S_2\times\ldots\times S_k)\setminus\{s^1,s^2,\ldots,s^n\}.$$

Claim. A (possibly very crude) upper bound is given by $\frac{n^k-1}{n-1}$.

Proof. We will prove this by induction on $k$.

For $k=1$, there is no problem. The set $S_1\setminus\{s^1,s^2,\ldots,s^n\}$ is a Cartesian product with one factor, so we are done: the upper bound is $1$ in this case.

For $k\to k+1$, note that we can rewrite the set as follows: \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} which is (if we omit the sets that appear more than once in the first union) a disjoint union of at most $n$ sets of the form $$(S_1\times S_2\times\ldots\times S_k\times\{s_{k+1}^j\})\setminus\{s^1,s^2,\ldots,s^n\},$$ and a single Cartesian product of $k+1$ sets. By the induction hypothesis, each set $$(S_1\times S_2\times\ldots\times S_k\times\{s_{k+1}^j\})\setminus\{s^1,s^2,\ldots,s^n\}$$ can be written as a disjoint union of at most $\frac{n^k-1}{n-1}$ Cartesian products. Therefore our set can be written as a disjoint union of at most $n\frac{n^k-1}{n-1}+1 = \frac{n^{k+1}-1}{n-1}$ Cartesian products (with $k+1$ factors each, of course). $\square$

Note that finding better bounds might require more sophisticated combinatorial methods.

-
Ummm ... In case $n=1$, $\frac{n^k-1}{n-1}$ should be interpreted as $k$. – Dejan Govc Apr 4 '13 at 21:14
Thanks for your answer. It got me thinking a little more, and I wonder now if I cannot get to $k{\cdot}n$, by representing $S$ as $((S_1 \setminus \{ s^1 \}) \times \ldots \times S_k) \cup (\{ s^1 \} \times \ldots \times S_k)$, then splitting $S_2$ in that second member, etc. In fact, I now suspect this could work for $S \setminus X$, where $X$ is an arbitrary Cartesian product from subsets of $S_1, \ldots, S_k$... Maybe someone can work a full answer, or I'll try myself. – Philippe Apr 5 '13 at 11:14