During Laci Babai’s course on graph isomorphism, one of the tools we encountered is the wreath product. Here I’ll give some intuitive descriptions of the wreath product .

To make sure we’re all on the same page, the wreath product for an arbitrary group and a permutation group is the semidirect product , where each is an automorphism of by permuting the coordinates.

That is, we fix some number and some group of permutations on , . The group we construct takes disjoint and independent versions of , , but also allows you to make “limited rearrangements according to “. There are two distinct ideas going on here; it’s the semidirect product that, if you tell it how two groups should interact, joins those two ideas into a single group.

### is a Graph Automorphism Group

There are two “trivial” wreath products, (where denotes the trivial group) and . is disjoint and independent versions of , with **no** interdependencies introduced by ; this is just .

Let be a graph with automorphism group . Claim: if you stick disjoint copies of next to each other, this new graph has automorphism group . To see this, of course some automorphisms apply elements “in parallel” to the different copies of . These automorphisms correspond to . But any rearrangement of the copies of is also an automorphism. All copies are isomorphic, so rearranging can be done without restriction by .

### Product Actions of Wreath Products

The previous paragraph shows that, if acts on a set , the wreath product acts naturally on . This is called the **sum action** (or “imprimitive action”, because it’s nearly always an imprimitive group action) of the wreath product. There is another natural action, called the **product action **(or “primitive action”). Here the domain is the set , and the action is defined by (1) applying elements of coordinate-wise and (2) permuting the coordinates with .

I think of this like a “simultaneous tracking” version of the sum action. In the sum action, we kept track of one point/vertex across copies of our graphs, and looked at where that point went when hit with a group element. In the product action, we track one point from each of the graphs simultaneously, and look at how as a whole those elements move.

### contains all extensions of by

It would be remiss to mention wreath products without mentioning the Kaluzhnin-Krasner theorem (English version). We say that the group is an extension of by if there is an exact sequence

**Theorem (Kaluzhnin-Krasner, 1951)** If is an extension of by , then is isomorphic to a subgroup of .

That is, is a group that’s big enough to contain all extensions of the two groups. In a sense that can probably be made more formal through order theory, is an “upper bound” on joining and together. Not bad!