2
$\begingroup$

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.

  • 0
    @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.2010-12-16
  • 0
    I'm a little bit confused. I will rethink and post an example.2010-12-16
  • 0
    @picakhu: Please post the *definitions* and not just an example. (An example is good, but please include definitions too).2010-12-16
  • 0
    I think posting this has made me realize that the question is actually much easier than I previously thought.2010-12-16
  • 0
    @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.2010-12-16
  • 0
    Thanks, you are quick at catching my mistakes. I do have a definition, just not sure how to write it out. They are ordered tuples.2010-12-16
  • 0
    @picakhu: If you cannot express the definition, then you don't really have a definition. In any case, under any reasonable interpretation of an "invariant coloring", $(1,1,0)$ is *not* invariant under the permutation $(2,3)$, because *it changes* when you apply the permutation (2,3). So either you are **not** considering colorings that are **invariant**, or you are defining equivalences between colorings as well, and then you need to say what *that* definition is.2010-12-16
  • 0
    Yes equivalences are defined between colorings, I failed to realize it was important to state that. Sorry.2010-12-16

2 Answers 2

0

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.

  • 0
    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.2010-12-17
  • 0
    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.2010-12-17
  • 1
    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.2010-12-17
1

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

  • 0
    I think this is right, but a bit too much for a much simpler problem, maybe I am wrong?2010-12-17
  • 1
    @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.2010-12-17