Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.