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!



Partitions of finite sets and their behavior under permutations of the set
(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?


