# Efficiently finding all pairs of disjoint sets

Say we have the letters $$\Omega = \{1,2,\dots n\}$$, and two sets of subsets of $$\Omega$$, $$S_1, S_2$$.

I want to find $$S_1 \cdot S_2 := \{(s_1,s_2) \in S_1 \times S_2: s_1 \cap s_2 = \emptyset \}$$. With the sets I'm working with, the cardinality of $$|S_1 \cdot S_2|$$ should be considerably smaller than $$|S_1||S_2|$$, thus I was wondering if there's a better solution. Is there an efficient data structure, which after preptime, can generate $$S_1 \cdot S_2$$, in $$O(|S_1 \cdot S_2|+n^c)$$ time? (so it takes polynomial time to create to encodes the pairings, and then constant time to return each pairing) I'd imagine there'd be a smart way to do this with posets, but a concrete structure eludes me currently.

If so, is there a way to be able to quickly update our structure, allowing us to add supersets of elements like so:

$$S_1 = S_1 \cup \{f(s_1,s_2) \supset s_1, \forall (s_1,s_2) \in S_1 \cdot S_2 \}$$ $$S_2 = S_2 \cup \{ g(s_1,s_2) \supset s_2, \forall (s_1,s_2) \in S_1 \cdot S_2\}$$

with complexity $$O(n^c|S_1 \cdot S_2|)$$, where $$f$$ and $$g$$ are some arbitrary functions with the stated superset properties?

• Can you please clarify my doubt. $S_1 \times S_2$ is set whose elements are pairs of form $(i,j) \text{ such that } i\in S_1 \text{ and } j\in S_2$. Then how can we use $\cap$ to compare $i \text{ and } j$. Oct 23, 2019 at 3:45
• $S_1$ and $S_2$ both contain subsets of $\Omega$ as elements. Oct 23, 2019 at 11:01
• – D.W.
Oct 23, 2019 at 16:57
• A useful keyword is "orthogonal vectors". Oct 29, 2019 at 14:05