Let $X=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}$ and $G=S_4$

(a) Show that $\phi \{x_1,x_2\}=\{\phi (x_1),\phi (x_2)\}$ determines an action of $S_4$ on $X$, where $\phi \in G$

(b) Determine the number of orbits of this action.

(a) I’m not really sure how to explain this but it comes as an intuitive action that if you act $\phi$ on $x_1$, it is just mapping $x_1$ to $\phi (x_1)$, which essentially is just mapping 1 to $\phi (1)$. But I’m not sure how to present this formally.

(b) Any hints on how I can do this? I’m not sure if I should write out all 24 elements in $S_4$ and use Burnside’s Theorem to find the number of orbits. But if I do so it might be too tedious. What happens when the it becomes larger? i.e $S_5$ acting on $X$; I don’t think I can write out all 120 elements.

Wondering if anyone can help with this?

  • $\begingroup$ What are $x_1$ and $x_2$ denoting? I guess they range over $\{1,2,3,4\}$. $\endgroup$ – Berci Nov 27 '18 at 11:10
  • $\begingroup$ @Berci Yes. OP is acting on a graph. $\endgroup$ – Pedro Tamaroff Nov 27 '18 at 11:16
  • $\begingroup$ If we take $g=(1,2) \in S_4$ then $g$ reverses the co-ordinates of each member of $X$ (I am assuming that the members of $X$ are ordered tuples rather than unordered sets). But $\{2,1\}, \{3,1\}$ etc, are not in $X$. So I am puzzled as to how the operation specified is an action on $X$ if $X$ only consists of the six points listed. Am I missing something ? $\endgroup$ – gandalf61 Nov 27 '18 at 11:20
  • $\begingroup$ @gandalf61 Yes it’s supposed to be an unordered set $\endgroup$ – Icycarus Nov 27 '18 at 11:34
  • $\begingroup$ @Icycarus But in that case each member of $G$ simply maps each member of $X$ to itself, so this is a very uninteresting action ! Is it possible that the operation that is intended is $\phi\{x_1,x_2\} = \{\phi(x_1), \phi(x_2)\}$ ? $\endgroup$ – gandalf61 Nov 27 '18 at 11:51

a) Note that $X$ contains all 2 elements subsets of $\{1,2,3,4\}$, so $X$ is indeed closed under the given map and that map satisfies the condition of being a group action.

b) Start with an element of $X$ and find its orbit. If there's any element left off, find its orbit too, and so on..


a) To formally show that $\phi\{x_1,x_2\}=\{\phi(x_1),\phi(x_2)\}$ is an action, you need to show two things:

1) $e\{x_1,x_2\}=\{x_1,x_2\} \space \forall \{x_1,x_2\} \in X$ where $e$ is the identity in $G$.

2) $\phi_1(\phi_2\{x_1,x_2\}) = (\phi_1 \phi_2)\{x_1,x_2\} \space \forall \{x_1,x_2\} \in X \space \forall \phi_1, \phi_2 \in G$

These are both straightforward.

b) Given two elements of $X$, think about how you can find a member of $G$ that maps one to the other (in fact, there is more than one as user25959 hints at above). This shows that $G$ acts transitively on $X$, so there is only one orbit.

  • $\begingroup$ i) the identity element is (1)(2)(3)(4) so applying $e\{x_1,x_2\}=\{x_1,x_2\}$ so it’s straightforward. How about (ii)? How do we go about showing it? $\endgroup$ – Icycarus Nov 27 '18 at 20:17
  • $\begingroup$ @Icycarus For (ii) here is an example. To find a permutation in $g \in G$ that maps $\{1.2\}$ to $\{3,4\}$, you could start by requiring $g$ to map $1$ to $3$ and $2$ to $4$. Now $3$ can either map to $1$, which gives $g=(13)(24)$, or $3$ can map to $2$ which gives $g=(1324)$. Note that $3$ cannot map to $4$ because $2$ already maps to $4$. Alternatively, you can require $g$ to map $1$ to $4$ and $2$ to $3$, which gives $g=(14)(23)$ or $g=(1423)$. So there are four possibilities for $g$. $\endgroup$ – gandalf61 Nov 28 '18 at 8:54

The stabilizer of $\{i,j\}$ consists of the permutations $e, (ij), (kl)$, and $(ij)(kl)$ where $k,l$ are the "other two" elements of $\{1,2,3,4\}$. So by the orbit-stabilizer theorem, $|Orb_{\{i,j\}}|\cdot 4 = |S_4|= 24$.


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.