Polyhedra from Cayley Graphs I was playing around with the Cayley graphs for some simple groups today and stumbled across something interesting, but can't quite figure out if there's something deeper going on. Here's what I did:
Consider the multiplicative group of the integers mod p, $\mathbb{Z}_{p}^{\times}$. We can generate $\mathbb{Z}_{p}^{\times}$ with any single element and obtain a simple Cayley graph. However, consider the Cayley graph generated by all primes strictly less than p, i.e. let $S=\{[a]: a \text{ is prime and } a<p\}$ and let $\Gamma_{p}$ be the Cayley graph $\Gamma_{p} = (\mathbb{Z}_{p}^{\times}, S)$.
Here is the Mathematica code I was using to generate some of the graphs:
plotGraph[p_] := (
  primesN := Table[Prime[n], {n, PrimePi[p] - 1}]; (*get generators*)

  (*function to compute adjacency matrix entries*)
  f[i_, j_] := (If[MemberQ[Mod[i*primesN, p], j], Return[1]];0); 

  M := Array[f, {p - 1, p - 1}]; (*create adjacency matrix*)
  MatrixForm[M] 
  GraphPlot3D[M, VertexLabeling -> True]
  )

I noticed that if n is not prime (and of course, $\mathbb{Z}_{n}-\{[0]\}$ is not a group), then the graph $\Gamma_{n}$ is really not interesting. However, when p is prime, the graphs have some nice structure. p=2 is a point, p=3 is a line segment, p=5 a square, p=7 an octahedron, p=11 looks like a pentagonal antiprism. However, I don't know if there is a pattern, or basically what's going on here. Does anyone have any insight?
 A: This does not exactly answer but... there's pictures! :)
I changed to code into

Needs["TetGenLink`"];
plot[p_] := Module[{pts},
  pts = First@ Cases[
     GraphPlot3D@ Flatten@
       Table[i -> Mod[i q, p], 
         {i, 1, p - 1}, {q, Prime[Range[PrimePi[p] - 1]]}],
     Pattern[s, Rule[VertexCoordinateRules, c_]] :> c, Infinity];
  Graphics3D@ GraphicsComplex[pts, Polygon[TetGenConvexHull[pts]]]
  ]

Now saying
GraphicsGrid[Partition[plot /@ Prime[Range[3, 11]], 3]]

gets us 

TetGenConvexHull only gets us a triangulation of the convex hull, so there are edges in these pictures that are only apparent.
A: You will always get a vertex-transitive graph with $p - 1$ vertices, where the number of edges at each vertex is the cardinality of $S \cup S^{-1}$ (where $S^{-1}$ means the set of inverses of the generators in $S$.)
For the case $p = 5$, we have $[2]^{-1} = [3]$, so we have a 2-regular graph on 4 vertices, which is a square. For $p = 7$, we have $[2]^{-1} = [4]$, while $[3]^{-1} = [5]$, so $S \cup S^{-1} = \{[2],[3],[4],[5]\}$ and we have a 4-regular graph on 6 vertices. Moreover, since $[2][5] = [3]$, etc., we get many 3-cycles (triangles).
For the small numbers, these considerations force the results you give. However, for $p = 11$ the graph is 8-regular, so it's not actually a pentagonal antiprism. In fact, the graph is not planar, so it's not a polyhedron (but it can probably be drawn in the pentagonal antiprism with extra diagonals.) And for $p > 13$, the graphs are at least 6-regular, hence cannot be planar (so are not the graphs of polyhedra.) The same is actually true for $p = 13$, where $S \cup S^{-1} = \{[2],[3],[5],[6],[7],[8],[9],[11]\}$.
I don't think it's true that it's less interesting when $p$ is not prime. In this case, the number of vertices is $\phi(p)$, the cardinality of $\mathbb{Z}_p^\times$, and you will need to restrict your set $S$ to the primes which don't divide $p$. For $p = 4$ or $p = 6$ you get a line segment, same as with $p=3$; with $p = 8$ you get a tetrahedron; with $p = 9$ you get an octahedron; $p = 10$ gives a square, etc.
