wreath product and automorphism groups of graphs

Question

I'm working with automorphism groups of graphs and I have a problem understanding the wreath product of two groups. I also wish to see some examples of graphs, other than Kn,n, whose automorphism group include wreath product of Sn.

Answer 1

Short version: The wreath product has two parts, the local swirl and the global swirl. Assuming we want both the local and global swirls to be full symmetric groups (on n and m points), there are only two possible final graphs per size of local and global. The local can be discrete, and global complete, giving the complete m-partite graph with n vertices per color, or the local can be complete and the global discrete giving the disjoint union of m copies of the complete graph on n vertices.

Wreath products in general: You have a graph with m subsets of n-vertices, each a different color. Local swirls do not change colors. Global swirls change colors, but we don't really try to decide what they do "locally" since who can really tell which red vertex corresponds to which blue vertex. Since we can change colors, we usually only mention the local swirl of a single color. Since we don't try to identify vertices of different colors, we usually only describe the global swirl on what it does to colors (rather than individual vertices).

For instance, a local swirl might take the red vertices $\color{red}{a}$ to $\color{red}{b}$ to $\color{red}{a}$ and leave $\color{red}{c}$ alone (and all the blues and greens left alone), whereas a global swirl might take reds to blues to reds and leave greens alone, maybe specifically $\color{red}{a}$ to $\color{blue}{a}$ to $\color{red}{a}$, $\color{red}{b}$ to $\color{blue}{b}$ to $\color{red}{b}$, $\color{red}{c}$ to $\color{blue}{c}$ to $\color{red}{c}$, etc.

Specializing to symmetric groups: Once we require the local and global swirls to be full symmetric groups, the possibilities are considerably narrowed. There are exactly two distinct graphs whose automorphism group is the full symmetric group: the null/discrete graph with no edges, and the complete graph with all edges. If we take one for the local structure, we need to take the other for the global structure to avoid getting the entire symmetric group rather than just the wreath product.

The first combination you are already familiar with as the complete m-partite graph: Take m copies of the discrete graph as the local graphs, and treat each local graph as a single vertex in the global graph, which is a complete graph. In other words, of the mn vertices involved, organize them into m collections of n each. Inside each collection there are no edges, but between collections there are all possible edges. The local swirl is the full symmetric group on the n involved vertices, since there is nothing to distinguish the vertices of a single color from one another. The global swirl is the symmetric group on the m local graphs (choosing any particular isomorphism between the local graphs) since there is nothing to distinguish one local graph from another.

In the m = 2 case, this is the complete bipartite graph. There are two colors, red and blue, and the red vertices form a local graph that is discrete (no edges between red vertices), and the blue vertices form a local graph that is discrete (no edges between blue vertices), but if you imagine all the red vertices smooshed into a red super-vertex and all the blue vertices smooshed into a blue super-vertex, then what is left is the complete graph on two super-vertices. The local swirls take reds to reds and blues to blues. The global swirls swap colors (so every red goes to a blue, and every blue goes to a red).

The second combination is a little silly: the disjoint union of complete graphs. In this case the local graphs are m copies of the complete graphs on n vertices, and the global graph is the discrete graph with no edges and m super-vertices. A red vertex is joined to every red vertex, but to no blue vertices. If you collapse the red vertices to a red super-vertex and the blue vertices to a blue super-vertex, then the result is the discrete graph with a red super-vertex and a blue super-vertex that are not connected at all. The local swirls take red vertices to red vertices, and blue vertices to blue vertices. The global swirls change colors (all reds go to blues, all blues go to reds).

Graphs with larger automorphism groups:

There are two other ways of combining local with global: (1) discrete with discrete gives a giant discrete graph with the full symmetric group on mn points as its automorphism group, and (2) complete with complete gives a giant complete graph with the full symmetric group on mn points as its automorphism group.

These are the only four graphs whose automorphism group contains the imprimitive wreath product of two symmetric groups, and only the first two "mixed" ones have automorphism group exactly equal to that wreath product.