Embedding Johnson Graph in $\mathbb{R}^2$

Question

Consider a Johnson graph $J(n,k)$ and denote its set of vertices by $V$ and its set of edges by $E$. Let $\bar{n}_k=\binom{n}{k}$. I am wondering whether there is a labeling $\{0,...,\bar{n}_k-1\}$ of its vertex set $V=\{v_0,...,v_{\bar{n}_k-1}\}$ such that when embedding the vertices at positions $v_l=(\cos(2\pi l\bar{n}_k^{-1}),\sin(2\pi l\bar{n}_k^{-1}))$ in $\mathbb{R}^2$ the set $$C=\{x\in \mathbb{R}^2| x = t(\cos(2\pi l\bar{n}_k^{-1}),\sin(2\pi l\bar{n}_k^{-1}))+(1-t)(\cos(2\pi l'\bar{n}_k^{-1}),\sin(2\pi l'\bar{n}_k^{-1}))\text{ with }\langle v_l,v_{l'}\rangle\in E, t\in[0,1]\}$$ is invariant under rotations of degrees being multiples of $2\pi \bar{n}_k^{-1}$. The set $C$ is the circular layout used for example by the python networkx package to draw graphs.

Since Johnson graphs are distance transitive I should be able accomplish this but this is just an intuition. I thought about drawing it and I started by drawing a cycle with $n$ vertices and then tried to fill in the remaining edges to get a Johnson graph. Unfortunately this didn't give me an idea on how to approach the problem or even if it is always correct. In the end I want to know if there is always a rotation invariant layout for Johnson Graphs in $\mathbb{R}^2$ as shown on the wikipedia page (https://en.wikipedia.org/wiki/Johnson_graph) .

Any help is highly appreciated!

Answer 1

This is almost always impossible. (Some exceptions: $J(n,1)$ is just the complete graph $K_n$, so of course it has such an embedding.)

If you were able to do what you want, then a rotation of the diagram by $2\pi / \binom nk$ would be an automorphism of the Johnson graph $J(n,k)$. Because we can repeat this rotation $\binom nk$ times before getting back to where we started, this is an element of order $\binom nk$ in the automorphism group.

But the automorphism group is $S_n$ in most cases ($S_n$ acts on the vertices, which are $k$-subsets of $\{1, 2,\dots, n\}$) except when $n=2k$ (in which case taking the complement is another possible automorphism). For most values of $n$ and $k$, $S_n$ doesn't have an element of order $\binom nk$. (Moreover, the subgroup generated by this element must act transitively on the vertices, which is even harder.)

(Even the diagram of $J(5,2)$ you see on Wikipedia doesn't have $10$-fold rotational symmetry! This would be impossible, since $S_5$ has no elements of order $10$. Instead, the symmetry is only $5$-fold.)

You can get some amount of symmetry. For example, if $n$ is prime, we can always get $n$-fold symmetry. To do this:

1. Partition the $\binom nk$ points around the circle into parts of size $n$ so that each part is the vertex set of a regular $n$-gon.
2. Let $\sigma \in S_n$ be the permutation which maps $i$ to $i+1$ for $i<n$, and maps $n$ to $1$. If this acts on the vertices of $J(n,k)$ (which are subsets of $\{1,2,\dots,n\}$ by permuting the elements of $\{1,2,\dots,n\}$, then it's an automorphism of $J(n,k)$.
3. When $n$ is prime, for any vertex $v$ of $J(n,k)$, the orbit $\{v, \sigma v, \sigma^2 v, \dots, \sigma^{n-1}v\}$ has size $n$, and these orbits partition $V(J(n,k))$. So just put each such orbit on the vertices of one of the regular $n$-gon we found in step $1$, in clockwise order.

When we've done this, $\sigma$ acts on $J(n,k)$ by rotating the diagram we get by $\frac{2\pi}{n}$, so the diagram has $n$-fold symmetry.

(When $n$ is not prime, this fails because not all orbits have size $n$. For example, if $n=6$ and $k=2$, the vertex $\{1,4\}$ is part of an orbit $\{\{1,4\}, \{2,5\}, \{3,6\}\}$ with only $3$ elements. Of course, when $n=6$ and $k=2$, we can't possibly hope for $6$-fold symmetry, since there are $15$ points.)