4
$\begingroup$

Consider the Cayley graph $G$ with vertex set the elements of the symmetric group $S_n$ and generating set the set of minimal transposition generators of the group $S_n$, that is the set $S=\{(12),(13),\ldots, (1n)\}$. Then, will the graph be always planar?

The graph is easily seen to be bipartite with one part the set of odd permutations and the other part the set of even permutations. Upto the group $S_3$ it is trivial to see why $G$ is planar. The first nontrivial part is when the group is $S_4$. The degree is $3$ in this case, but I don't see the complete regular bipartite graph $K_{3,3}$ explicitly. But can $G$ have a $K_{3,3}$ minor? I don't think so. Also, what if I replace the set $S$ with the set of all transpositions? Any hints? thanks beforehand.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

You already have an answer regarding the first part of your question, but this uses the fact that with your given generating set, the Cayley graph is $(n-1)$-regular. What if we pick the generating set $\{ (12), (12\cdots n)\}$?

So: there is a full characterisation, due to Maschke (1896), of which finite groups admit planar Cayley graphs with respect to some generating set. Such groups are called planar.

The finite group $A$ is planar if and only if $A = B_1 \times B_2$ with $B_1 = 1$ or $\mathbb{Z}_2$, and $B_2 \in \{ \mathbb{Z}_n, D_n, S_4, A_4, A_5 \mid n \in \mathbb{N} \}$.

A proof can be found e.g. here, and the original article is the (aptly) named [Maschke, H. The Representation of Finite Groups, Especially of the Rotation Groups of the Regular Bodies of Three-and Four-Dimensional Space, by Cayley's Color Diagrams. Amer. J. Math. 18 (1896), no. 2, 156–194.]. If you'd like to read it, a stable link is here.

In particular, $S_n$ for $n \geq 5$ admits no generating set such that its Cayley graph is planar, answering the second part of your question.

Improve this answer
$\endgroup$
10
  • $\begingroup$ thanks! just a small miss. The graphs have to connected right. otherwise we could have lot of counterexamples $\endgroup$
    – vidyarthi
    Apr 28, 2020 at 12:09
  • $\begingroup$ @vidyarthi A Cayley graph is always connected, yes. What counterexamples do you have in mind? $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Apr 28, 2020 at 12:12
  • $\begingroup$ why? just take $S_5$ with generating set $S=\{(12)\}$. I mean, if the generating set of the graph is not a generating set of the group, then we have a disconnected graph $\endgroup$
    – vidyarthi
    Apr 28, 2020 at 12:14
  • 1
    $\begingroup$ @vidyarthi If your set $S$ does not generate the group, then the graph is not a Cayley graph. This is part of the definition of a Cayley graph. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Apr 28, 2020 at 12:15
  • $\begingroup$ oh! I am used to thinking that the set of generator of the graph need not generate the group. Anyway, thanks for pointing out that $\endgroup$
    – vidyarthi
    Apr 28, 2020 at 12:20
10
$\begingroup$

Your graph $G$ will not be planar for all $n \geq 5$. To see this, we use the well-known fact that every bipartite planar graph $H$ satisfies $|E(H)| \leq 2|V(H)|-4$, and hence has average degree less than $4$. Since your Cayley graph $G$ is $(n-1)$-regular and bipartite, it is not planar for all $n \geq 5$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks, can it be said to $k-$ planar, for some $k$? $\endgroup$
    – vidyarthi
    Apr 28, 2020 at 10:55
  • 1
    $\begingroup$ No, if $k$ is fixed, $k$-planar graphs also have bounded average degree, $O(\sqrt{k})$ if I recall correctly. $\endgroup$
    – Tony Huynh
    Apr 28, 2020 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.