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.)
Best Answer
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.