Partitions of finite sets and their behavior under permutations of the set

Question

The following seems to be useful, and probably well-known, but I can't find a reference for it. If anyone can point me to a textbook or paper which states it, then I'd be grateful.

Consider a partition of $(A, B)$ of a finite set $X$. That is, $X = A \cup B$ and $A \cap B = \emptyset$. Suppose further that the size of $X$, $|X|$, is even and $A$ and $B$ have the same size, $|A| = |B|$. Suppose that $\{\sigma_1, \sigma_2,\ldots, \sigma_k \}$ is a set of $k$ permutations of $X$. For $j \leq k$, we can define partition subsets of $X$ as follows:

$X_{U_0U_1 \ldots U_j} = \{x \in X: x\in U_0, \sigma_1(x) \in U_1, \sigma_2\sigma_1(x) \in U_2, \ldots, \sigma_j \ldots \sigma_2\sigma_1(x) \in U_j\}$ where each $U_i$ is $A$ or $B$.

By definition $X_A = A$ and $X_B = B$. For $j = 1$, $X_{AA}$ is the set of elements of $A$ that stay in $A$ under $\sigma_1$, $X_{AB}$ is the set of elements of $A$ that move to $B$ under $\sigma_1$, $X_{BA}$ is the set of elements of B that move to $A$ under $\sigma_1$, and $X_{BB}$ is the set of elements of $B$ that stay in $B$ under $\sigma_1$. For $j = 2$, $X_{ABB}$ is the set of elements of $X$ which start off in $A$ then $\sigma_1$ takes them to $B$, and $\sigma_2$ leaves them in $B$, and so on.

Note that $X_A = X_{AA} \cup X_{AB}$ and $X_B = X_{BA} \cup X_{BB}$. More generally, for $j < k$, $X_{U_0U_1 \ldots U_j}$ = $X_{U_0U_1 \ldots U_jA} \cup X_{U_0U_1 \ldots U_jB}$.

Clearly, for each $j \leq k$, and for any $\{\sigma_1, \sigma_2,\ldots, \sigma_k \}$ set of $k$ permutations of $X$, the $X_{U_0U_1 \ldots U_j}$ sets define a partition of $X$ into $2^{j+1}$ partition subsets of $X$. With this notation in mind, we have the following partitions of $X$:

$$ X = X_A \cup X_B$$

$$ X = X_{AA} \cup X_{AB} \cup X_{BA} \cup X_{BB}$$

$$ X = X_{AAA} \cup X_{AAB} \cup X_{ABA} \cup X_{ABB} \cup X_{BAA} \cup X_{BAB} \cup X_{BBA} \cup X_{BBB}$$

and so on.

For any such partition, we can pair up the subsets by matching opposite subsets defined by saying that $X_{U_0U_1 \ldots U_j}$ is opposite to $X_{U'_0U'_1 \ldots U'_j}$, where if $U_i = A$, then $U'_i = B$, and vice versa. For example, $X_{A}$ is opposite to $X_{B}$, $X_{AB}$ is opposite to $X_{BA}$, and $X_{ABA}$ is opposite to $X_{BAB}$.

Now here's the statement which I think should be well-known, but cannot track down:

Let $X$ be any finite set of even size and let $A$ and $B$ be a partition of $X$ into equal size subsets. Let $\{\sigma_1, \sigma_2,\ldots, \sigma_k \}$ of $X$ be any set of permutations of $X$. If we define the partition subsets as above, then opposite sets have the same size.

I can prove this (though in a rather clunky manner). However, if this well-known and/or there is a simple proof, then I'd be very happy to see it!

Answer 1

(Not an answer, but too long for a comment.) What if $X = \{1,2,3,4,5,6\}$, $A=\{1,2,3\}$, and $B=\{4,5,6\}$; and $\sigma_1=(3,6)$, $\sigma_2=(2,6)\sigma_1^{-1} = (2,6,3)$. Anyway $\sigma_2 \sigma_1 = (2,6)$.

Now

• $X_A = A = \{1,2,3\}$,
• $X_{AA} = X_A \cap \sigma_1^{-1}(A) = A \cap \{1,2,6\} = \{1,2\}$, and
• $X_{AAA} = X_{AA} \cap (\sigma_2 \sigma_1)^{-1}(A) = \{1,2\} \cap \{1,3,6\} = \{1\}$.

Meanwhile,

• $X_B = B = \{4,5,6\}$,
• $X_{BB} = X_B \cap \sigma_1^{-1}(B) = B \cap \{4,5,3\} = \{4,5\}$, and
• $X_{BBB} = X_{BB} \cap (\sigma_2 \sigma_1)^{-1}(B) = \{4,5\} \cap \{4,5,2\} = \{4,5\}$.

It looks like $|X_{AAA}|=1$ but $|X_{BBB}|=2$. Can you please clarify?