Informally, I am given a subset $Q$ of a Cartesian product $A_1\times\ldots \times A_n$ and I would like to write $Q$ as a disjoint sum of Cartesian products of subsets of the $A_i$. I would like the decomposition to be optimal in some sense—e.g. the number of terms in the disjoint sum is as small as possible.

Here's a formal statement of the problem:

Given a collection of finite disjoint sets $A_1, \ldots, A_n$ and a subset $Q$ of the Cartesian product $A_1 \times A_2 \times \ldots \times A_n$, find an integer $k$ and subsets $\{ B_{i,j} \subseteq A_j\;: \; i\in [1,k], j\in[1,n]\}$ such that

$$Q \equiv \bigcup_{i=1}^k B_{i,1} \times \ldots B_{i,n} $$

and where $k$ is the smallest integer for which such a decomposition is possible.

I feel like this problem must have been asked before, but I haven't been able to find a solution online, perhaps because I lack the necessary terminology.

  • 1
    $\begingroup$ A note on terminology: It's not sum, but rather union. $\endgroup$ – Justin Benfield Jan 5 '17 at 4:50
  • $\begingroup$ Are the $A_i$'s supposed to be finite, because if not, I'm pretty sure I can construct an example where you need infinitely many $i$'s. $\endgroup$ – Justin Benfield Jan 5 '17 at 4:57
  • $\begingroup$ If $n=2$ and $A_1=A_2$ and $Q=\{(a,a):a\in A\}$ then the best you can do is use one term in the disjoint sum for each element of $A.$ Are you looking for a general theorem or are you looking for an algorithm to find an optimal decomposition for a given set $Q$ in the case where all the sets are finite? $\endgroup$ – bof Jan 5 '17 at 5:12
  • $\begingroup$ Ultimately, I'm looking for an algorithm for finite sets. I'm not sure if that counts as a math question, but I figure even finding the right terminology would help if this sort of problem is well-known. $\endgroup$ – user326210 Jan 5 '17 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.