I am trying to figure out a good way of finding the intersection of two partitioned subsets of a set (or what to call what I'm trying to do so I can read something about it).
Let's say I have two subsets, ABC and BCDE. The first is partitioned into A/BC (part A vs part BC) and the second is partitioned into B/CDE (part B vs part CDE). Whatever the two subsets are, the partitions are always bipartite.
Now I want to combine these subsets, retaining the partitions so that I have A/B/C/DE. I may implicitly be treating the fact of the two subsets as a higher-order partition. This seems to me some sort of intersection of partitions (hence title).
It seems there should be a clear algorithm for what I'm doing here but I just can't grasp it. To make things worse, I need to be able to scale this up to more than two subsets (but the partitions are always bipartite). Any advice would be appreciated.
Thanks for reading–
Best Answer
You can equivalently think of partitions as equivalence relations, with elements in the same piece of the partition labelled as equivalent. So the partition in the first subset $S_1$ is given by the equivalence $$B \sim_1 C,$$ and the partition in the second subset $S_2$ is given by the equivalence $$C \sim_2 D \sim_2 E.$$ We can even suppose that we have more subsets, $S_1,...,S_n$, each with a partition defined by the equivalence relation $\sim_n$. In order to match your operation, it's actually better if we extend these relations to the union $\bigcup_1^n S_i$ by additionally declaring $X \sim_i Y$ if $X, Y \notin S_i$.
Now I define a final equivalence relation $\sim$ by $X \sim Y \iff X \sim_i Y \;\forall\; i$. Translating this back into a partition should match the operation you've defined.