3
$\begingroup$

$\mathbf{Question:}$ Let $G$ be a finite group and $g\in G$ be an element of even order. Prove that the elements of the group can be coloured using two colours in such a way that $x$ and $gx$ have different colours $\forall x\in G$.

$\mathbf{Attempt:}$ By Lagrange's theorem, $G$ is of even order, say $2n$. We "bifurcate" $G$ into two equal halves, say $A= \{x_1,x_2,...,x_n\}$ and $B=\{y_1,y_2,...y_n\}$, where $x_1=e$ and $y_i=gx_i, \ 1\leq i \leq n$. So, $y_1=g$ , $A\cup B=G$ and $A\cap B=\emptyset$

Clearly, $\phi_1:A \to B$ defined by $\phi_1(x_i)=gx_i$ is an injection, consequently, it is a bijection.

Again, $\phi_2:B \to A$ defined by $\phi_2(y_i)=gy_i=g^2x_i$ sends $x_i's$ back to $A$.

If we give the elements of $A$ the same colour and the elements of $B$ another, the colouring is done.

Is this correct? Kindly Verify.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Aloizio Macedo
    Commented Sep 7, 2019 at 16:14

2 Answers 2

3
$\begingroup$

Well, but what if $g$ does not generate the whole group?

What is not a priori clear is whether what you give as the partitioning of $G$ into two sets is indeed well-defined. Indeed, you were asked to show that there is infact such a partition that is well-defined. There of course would NOT be well-defined parition if $g$ had odd order.

This is now I would do this: First partition $G$ into right cosets $X_1,X_2, \ldots X_r$ of $\langle g \rangle$ i.e., for each $j$ there is an $x_j \in G$ such that $X_j =\{g^ix_j; $ $i \in \mathbb{Z}\}$ [fix such an $x_j$ for each $j=1,2,\ldots, r$]. Next parition $G$ into two sets $G_1$ and $G_2$ as follows:

(A) For each $y \in X_j$, write $y=g^ix_j$ for some integer $i$, where $x_j$ is as specified above, and $i$ is a nonegqative integer no greater than ord$(g)-1$. Note that there is exactly one such way to respresent each $y \in G$ as above. Now writing $y=g^ix_j$ as above, let exp$(y)$ be the integer $i$. Then iff exp$(y)$ is odd then put $y$ into $G_1$ and if exp$(y)$ is even then put $y$ into $G_2$. As there is exactly one way to write each $y \in G$ as above, this partitioning of $G$ into $G_1$ and $G_2$ is well-defined.

[So what I said above is I think what you were trying to get at, but what was needed was for you to take care to specify the partitioning precisely.]

So now it suffices to show that $y \in G_1 \Leftrightarrow gy \in G_2$ for each $y \in G$, and then we are done.To this end, write $y=g^ix_j$ as specified above. Then exp$(g)=i$, and $gy=g^{i+1}x_j$ if $i < $ord$(g)-1$ and $g(y)=y^0x_j$ if $i=$ord$(g)-1$. So exp$(gy) = $exp$(y)+1$ if exp$(y) < $ ord$(g)-1$, and exp$(gy)= 0$ if exp$(y)=$ord$(g)-1$. But then as ord$(g)$ is even it follows that exp$(gy)$ is even iff exp$(y)$ is odd, and so $gy$ must be put into $G_2$ if $y$ is put into $G_1$ by (A) above.


If you are familiar with Cayley graphs then the Cayley graph where the vertices are elements of $G$ and where $x$ and $y$ form an edge iff $y \in \{gx, g^{-1}x\}$ is either a collection of vertex-disjoint cycles of length ord$(g)$ [if ord$(g) \ge 3$], or is a perfect matching [if ord$(g)=2$]. This graph is bipartite if ord$(g)$ is even. Then a proper-2-colouring of this graph corresponds to a coloring where $x$ and $gx$ are given different colors for each $x \in G$. Such a proper 2-colouring exists if ord($g$) is even, as we already observed, this graph is then bipartite.

$\endgroup$
5
  • $\begingroup$ I have realized what I skipped over $\endgroup$ Commented Sep 7, 2019 at 5:47
  • $\begingroup$ A small doubt: Why can't we have $g^ix_j=g^mx_n$ where $i$ is even and $m$ is odd ($j$ and $n$ can be anything)? Is this because cosets form a partition? Is this why we can't have it when $n \neq j$ ? ( Evident when $n=j$) $\endgroup$ Commented Sep 7, 2019 at 6:05
  • $\begingroup$ Because $x_n$ and $x_j$ are not in the same coset of $\langle g \rangle$; there is no $i$ s.t. $g^ix_j = x_n$ which implies that there is no $i$ and $m$ s.t. $g^ix_j=g^mx_n$. So yes, the cosets form a partition. $\endgroup$
    – Mike
    Commented Sep 7, 2019 at 12:29
  • 1
    $\begingroup$ Got it. Would revise this answer. Thanks a lot for your time :) I learned something. $\endgroup$ Commented Sep 7, 2019 at 12:33
  • 1
    $\begingroup$ Glad I could help! $\endgroup$
    – Mike
    Commented Sep 7, 2019 at 12:33
3
$\begingroup$

Well done! It's a good proof, but it could be improved.


Let's go line-by-line.

By Lagrange's theorem, $G$ is of even order, say $2n$.

Correct. It might be best to specify that this is due to $|g|$ being even.

We "bifurcate" $G$ into two equal halves, say $A= \{x_1,x_2,...,x_n\}$ and $B=\{y_1,y_2,...y_n\}$, where $x_1=e$ and $y_i=gx_i, \ 1\leq i \leq n$.

I'm not sure of the terminology but, yes, this is okay.

So, $y_1=g$ , $A\cup B=G$ and $A\cap B=\emptyset$

Yep.

Clearly, $\phi_1:A \to B$ defined by $\phi_1(x_i)=gx_i$ is an injection, consequently, it is a bijection.

This is fine.

Again, $\phi_2:B \to A$ defined by $\phi_2(y_i)=gy_i=g^2x_i$ sends $x_i's$ back to $A$.

I'm not sure why this is necessary, but okay.

If we give the elements of $A$ the same colour and the elements of $B$ another, the colouring is done.

Yes, that'll do.

$\endgroup$
1
  • 1
    $\begingroup$ Lovely! I really appreciate your answer :) $\endgroup$ Commented Sep 5, 2019 at 3:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .