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!

| cite | improve this question | | | | |

(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)$.


  • $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\}$.


  • $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?

| cite | improve this answer | | | | |
  • 1
    $\begingroup$ A bit simpler counterexample: $A=\{1,2\}$, $B=\{3,4\}$, $\sigma_1=(2,3)$, $\sigma_2=(2,4)$, implying that $X_{AAA}=\{1\}$ and $X_{BBB}=\emptyset$. $\endgroup$ – Max Alekseyev Jan 2 '18 at 17:30
  • $\begingroup$ Yes I could have removed 1 and 4 from my example. Thank you. $\endgroup$ – Zach Teitler Jan 2 '18 at 17:40
  • $\begingroup$ More interestingly what conditions restore the claim? All the permutations are powers of the same $n$-cycle maybe? $\endgroup$ – Zach Teitler Jan 2 '18 at 17:43
  • 1
    $\begingroup$ E.g., if there exists an involution $\iota$ commutative with each $\sigma_i$ such that $\iota(A)=B$. $\endgroup$ – Max Alekseyev Jan 2 '18 at 17:52
  • 1
    $\begingroup$ Conjecture: Let $X$ be a finite set of even size, and $A$ and $B$ be a partition of $X$ into two equal-sized subsets. If $\sigma_1$ and $\sigma_2$ are two permutations of $X$ such that the sign of the permutation $\sigma_i$ is equal to $-1^{|\sigma_i(A) \cap B|}$, for $i = 1, 2$, then the sign of $\sigma_2.\sigma_1$ is equal to $-1^{|\sigma_2.\sigma_1(A) \cap B|}$. If true, this would give me a nice relationship to work with on partitions of finite sets. $\endgroup$ – user304582 Jan 3 '18 at 18:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.