3
$\begingroup$

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

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Ummm ... In case $n=1$, $\frac{n^k-1}{n-1}$ should be interpreted as $k$. $\endgroup$ Commented Apr 4, 2013 at 21:14
  • $\begingroup$ 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. $\endgroup$ Commented Apr 5, 2013 at 11:14

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.