1

I couldn't quite figure out what the automorphism group of a complete bipartite graph $\Gamma (K_{r,s})$ is isomorphic to. I did some back-of-the-envelope calculations and found that $\Gamma (K_{r,s})$ has an order of $(s-1)!$ when $r = 1$ and $s \geq 2$, and has an order of $2(r!s!)$ when $ r, s \geq 2$ (I don't have a proof of that. I might be wrong.) but I'm not aware of any groups that might be isomorphic to $\Gamma (K_{r,s})$ as my knowledge of group theory is rather elementary.

Pecfex
  • 25
  • 1
    it is the wreath product of $S_r$ and $S_s$, where $S_r$ and $S_s$ group of all permutations on the set of $r$ and $s$ elements respectively. – boil Aug 01 '21 at 03:11

1 Answers1

3

Your computations of the number of automorphisms aren't quite right in general, though they are close.

Hints: Clearly, the $r$ nodes on one side are all equivalent to each other, and can be freely permuted; what is the symmetry group of $r$ identical objects? Given that similarly the $s$ nodes on the other are also all equivalent, we could consider an arbitrary permutation of those as well; how do we combine these two symmetry groups together to get a larger one? And finally, are there any special values of $r,s$ for which there is an extra symmetry?

not all wrong
  • 16,178
  • 2
  • 35
  • 57
  • Thanks, I just noticed errors in my calculations and yes, I did think about the vertices in each partition being freely permutable but my problem is I still don't know what that is even after the hint because, like I mentioned, I don't know group theory. – Pecfex Feb 08 '21 at 13:51
  • @Pecfex Well, by definition, the symmetry group of $r$ identical objects is the symmetric group of degree $r$, written $S_r$. And when you have two groups $G_1,G_2$ acting in ways that don't interfere with each other, then the larger product group $G_1 \times G_2$ (which consists of all symmetry transformations that are an arbitrary combination $(g_1,g_2)$ of transformations in each group) also acts. These are all the ingredients you need to build up the answer. – not all wrong Feb 08 '21 at 14:03