# 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: It is impolite to post in the imperative mode, as if you are giving the group an assignment or a homework problem to do for you. If this is homework, consider tagging it as [homework]. In any case, it is helpful if you say *why& you are interested in a solution, and what your thoughts are for it so far. –  Arturo Magidin Dec 16 '10 at 18:14
Thanks, will remember that. –  picakhu Dec 16 '10 at 18:26
@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

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