# Bijection of 2-colorings and permutation equivalence classes

Let $G$ be a group of permutations of $n$ objects. Let subsets $A$,$B$ of the objects be equivalent if $A=g(B)$ for some $g \in G$. Is there a way to show that a bijection exists between the equivalence classes and the $2$-colorings of the objects that are invariant under those permutations in $G$?

So Far, I have verified that it works(their cardinalities are the same) for a few cases I tried, but I do not see how it can be generalized.

I will post an example, the definition should be clear from the example.

let $G=\{e,(2 3)\}$, $n=3$ then, we have 8 subsets and 6 equivalent subsets. namely $\{\}, \{1\},\{\{2\},\{3\}\}, \{\{1,2\},\{1,3\}\},\{2,3\},\{1,2,3\}$ and the invarient transformations are. $\{1,1,1\},\{1,1,0\} \sim \{1,0,1\},\{0,1,1\},\{1,0,0\},\{0,0,1\} \sim \{0,1,0\},\{0,0,0\}$

In this example applying (2 3) to {0,1,0} changes it to {0,0,1} and applying e, leaves it as it is.

-
@picakhu: Given your comment to my (now deleted) answer, clearly we are not interpreting "coloring of the objects" or "coloring invariant under $G$" the same way. Please give your definitions. – Arturo Magidin Dec 16 '10 at 19:00
I'm a little bit confused. I will rethink and post an example. – picakhu Dec 16 '10 at 19:03
@picakhu: Please post the definitions and not just an example. (An example is good, but please include definitions too). – Arturo Magidin Dec 16 '10 at 19:03
I think posting this has made me realize that the question is actually much easier than I previously thought. – picakhu Dec 16 '10 at 19:17
@picakhu: You don't have equivalent subgroups, because your equivalences are not defined on subgroups. They are subsets. Your notation for colorings makes little sense to me. Are they ordered tuples or are they sets (how many are one color, how many are a different color)? Not the latter, because then "{1,0,0}" would be "the same" as "{0,1,0}". Why is coloring 1 and 2 the same color and 3 a different color "the same" as coloring 1 and 3 the same color and 2 a different color? If you don't have definitions, then you don't have a concept. – Arturo Magidin Dec 16 '10 at 19:18

So, what you are actually doing is this:

Let $X$ be a set, and let $G$ be a subgroup of $S_X$, the group of permutations on $X$.

We define two equivalence relations, one, let's call it $\sim$, on $\mathcal{P}(X)$, the power set of $X$, and one, let's call it $\equiv$, on the set of functions $2^X = \{f\colon X\to \{0,1\}\}$, which we think of as the $2$-colorings of $X$. We define: \begin{align*} A\sim B &\Longleftrightarrow \text{there exists $\sigma\in G$ such that $\sigma(A)=B$}\\ f\equiv g &\Longleftrightarrow \text{there exists $\sigma\in G$ such that $f\circ\sigma = g$.} \end{align*} The question is whether there is a bijection between $\mathcal{P}(X)/\sim$ and $2^X/\equiv$.

The key is that there is a natural identification of $2^X$ with $\mathcal{P}(X)$, by mapping $f\colon X\to\{0,1\}$ to the subset $f^{-1}(1) = \{x\in X\mid f(x)=1\}$, and mapping $A\subseteq X$ to $\chi_A$, the characteristic function of $A$.

Define $\mathcal{F}\colon \mathcal{P}(X)/\sim \to 2^X/\equiv$ as follows: given a class $[A] = \{ B\in\mathcal{P}(X)\mid A\sim B\}$, we let $$\mathcal{F}([A]) = \{ \chi_B\mid B\in [A]\}.$$

First, I claim this is well defined: that is, I claim that $\mathcal{F}([A])$ is an equivalence class modulo $\equiv$.

Suppose $A\sim B$. Then there exists $\sigma\in G$ such that $\sigma(A)=B$. I claim that $\chi_B\circ\sigma = \chi_A$. Indeed, let $x\in X$. If $x\in A$, then $\sigma(x)\in B$, so $\chi_B\circ\sigma(x) = 1 = \chi_A(x)$. And if $x\notin A$, then $\sigma(x)\notin B$ (since $A=\sigma^{-1}(B)$), so $\chi_B\sigma(x) = 0 = \chi_A(x)$. Thus, $\chi_B\equiv \chi_A$.

Conversely, suppose that $f\in 2^X$ is equivalent to $\chi_A$. Then there exists $\tau\in G$ such that $f\circ\tau = \chi_A$. Let $B=\tau(A)$. I claim that $\chi_B=f$. Indeed, let $x\in X$. Then $f(\tau(x))=1$ if and only if $x\in A$, if and only if $\tau(x)\in B$. So $f(y)=1$ if and only if $y\in B$. Note that $B\sim A$.

Therefore, every element of $[A]$ gets mapped to an element of $$\langle \chi_A \rangle = \{ f\in 2^X\mid f\equiv \chi_A\}$$ and every element of $\langle\chi_A\rangle$ comes from an element of $[A]$. Thus, $\mathcal{F}$ is well defined.

Now, $\mathcal{F}$ is one-to-one: if $\mathcal{F}([A]) = \mathcal{F}([B])$, then $$\chi_B\in \langle \chi_B\rangle = \mathcal{F}([B]) = \mathcal{F}([A])=\langle \chi_A\rangle$$ so there exists $\sigma\in G$ such that $\chi_B\sigma = \chi_A$. that means that $x\in A$ if and only if $\sigma(x)\in B$, so $B=\sigma(A)$, hence $B\sim A$, so $[A]=[B]$.

And $\mathcal{F}$ is onto: let $\langle f\rangle$ be an equivalence class of $2^X/\equiv$. Let $A = f^{-1}(1)$. I claim that $\mathcal{F}([A])=\langle \chi_A\rangle = \langle f\rangle$. Indeed, $\chi_A = f$ by construction, so $f\in\langle\chi_A\rangle$, hence $\langle f\rangle = \langle \chi_A\rangle = \mathcal{F}([A])$.

Therefore, $\mathcal{F}$ is a bijection between $\mathcal{P}(X)/\sim$ and $2^X/\equiv$.

However, I want to add that I think it is fair to say that your nomenclature is misleading/nonstandard. I would take that a $2$-coloring of $X$ is invariant under $G$ to mean that if $f\colon X\to\{0,1\}$ is the $2$-coloring, then $f\circ \sigma = f$ for all $\sigma\in G$.

-
I think this is right, but a bit too much for a much simpler problem, maybe I am wrong? – picakhu Dec 17 '10 at 2:58
@picakhu: I did the details because you seem so confused (you cannot even state the equivalence relation you are using on colorings). But at the heart, it's just the fact that $\mathcal{P}(X)$ is "the same" as $2^X$, and the equivalence relations are given by the same rule. – Arturo Magidin Dec 17 '10 at 2:59

I think this will work.

Consider the bijection where coloring $\{...,x_i=1,...\}$ means that object $i$ is included in our set, then the rest follows.

-
I certainly have no idea what that means, but since I'm not the one grading you, who cares what I think? I'll be happy to remove my answer if it was not helpful. – Arturo Magidin Dec 17 '10 at 2:54
what I am saying is that we have a 2-coloring. So, either {...,$x_i$=1 or 0,...} If $x_i=0$ then we exclude i from our set, else we include it. So, now we can apply the permutations to the coloring set or the numerical sets. A permutation of the coloring set maps it to another coloring. – picakhu Dec 17 '10 at 2:56
This is exactly what I pointed out in my answer: your "colorings" are just functions from $X$ to $\{0,1\}$, and you are identifying each subset with its characteristic function. That is, you are identifying $\mathcal{P}(X)$ with $2^X$ in the obvious way, and your equivalence relation on $2^X$ is just the equivalence relation you have on $\mathcal{P}(X)$, translated. – Arturo Magidin Dec 17 '10 at 3:01