3
$\begingroup$

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 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?

  • 0
    Ah! I had assumed $\mathbb{Z}_{n}^{\times}$ was just different notation for the set of nonzero elements. *Now* it's fixed.2012-01-11

2 Answers 2

3

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

enter image description here

TetGenConvexHull only gets us a triangulation of the convex hull, so there are edges in these pictures that are only apparent.

  • 0
    Keep in mind that the position of the vertices in these pictures is fixed by Mma in some more or less random way---other arrangements different from the one picked might have more symmetry.2012-01-11
0

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.