20
$\begingroup$

Recall that an $(n,g)$-graph is a simple graph where each node has $n$ neighbors and the shortest cycle has length $g$, while an $(n,g)$-cage is $(n,g)$-graph with the minimum number of nodes.

The McGee graph is the unique $(3,7)$-cage. It looks like this:

McGee graph

Now, the unique $(3,6)$-cage is the Heawood graph, which has strong connections to the Fano plane and its symmetry group, $PGL(3,\mathbb{F}_2)$. The unique $(3,8)$-cage is the Tutte–Coxeter graph, which has strong connections to the Cremona–Richmond configuration and its symmetry group, $S_6$. These stories are fascinating and strongly parallel.

What about the McGee graph? All I know is what I read:

It has 24 nodes and 36 edges. Its symmetry group has 32 elements — which 32-element group is it? Its symmetry group doesn't act transitively on the nodes: there are two orbits, containing 16 and 8 nodes.

Is this graph associated to an interesting finite geometry, or not?

$\endgroup$
  • 8
    $\begingroup$ The Heawood and T/C graphs are both bipartite so there is an obvious geometric interpretation by taking the two parts to be "points" and "lines". The McGee graph is not bipartite, so any geometric connection will be more hidden. $\endgroup$ – Gordon Royle Aug 20 '15 at 10:09
  • 3
    $\begingroup$ The group is not a super-interesting group, it is SmallGroup(32,43) in either GAP or Magma, described as $(C_2 \times D_8) : C_2$. The standard picture of the McGee graph shows an 8-fold rotation hence the dihedral group, and presumably the other two $C_2$s can be seen in the picture. $\endgroup$ – Gordon Royle Aug 20 '15 at 10:43
  • $\begingroup$ +Gordon - how did you figure out this symmetry group? According to groupprops.subwiki.org/wiki/Holomorph_of_Z8 , SmallGroup(32,43) is the semidirect product of Z/8 with its automorphism group. $\endgroup$ – John Baez Sep 5 '15 at 12:16
  • 2
    $\begingroup$ The ring $\mathbb{Z}/8$ has just 4 invertible elements: 1, 3, 5 and 7. So, $\mathbb{Z}/8$ has $8 \times 4$ invertible transformations of the form $x \mapsto ax + b$. $\endgroup$ – John Baez Sep 9 '15 at 5:11
  • 2
    $\begingroup$ I got the automorphism group from another program (many will do it) but then used GAP to get its structure. $\endgroup$ – Gordon Royle Sep 9 '15 at 6:14
11
$\begingroup$

Genus 2 embedding of McGee graph

Edited 27 September 2016

(An earlier version of this answer incorrectly claimed to show that the genus of the McGee graph was 3. In fact, the genus of the McGee graph is 2. Thanks to Gordon Royle, who pointed out this mistake.)

The image above shows how to embed the McGee graph into a surface of genus 2. There are 10 oriented cycles here (8 of length 7, and 2 of length 8) which contain each edge twice with opposite orientations. So the Euler characteristic of the oriented surface in which the graph is embedded here is $\chi=24-36+10=-2$, and its genus is $g=2$.

We can prove that this is the minimum genus as follows:

Suppose we've embedded the graph in an orientable surface, so that the surface is decomposed into $F$ regions. These regions might not all be simply connected, so in general we will say that each has $b_i$ connected components to its boundary, and the $j$th connected component of the boundary of the $i$th region is comprised of $n_{i,j}$ edges of the graph, forming a cycle of the graph.

Since each of the 36 edges of the graph appears twice in these boundaries, we have:

$$\sum_{i=1}^F \sum_{j=1}^{b_i} n_{i,j} = 2 \times 36 = 72$$

But the smallest cycles in the graph have length 7, so:

$$7 \sum_{i=1}^F b_i \le 72$$

Since the $b_i$ are integers, it follows that:

$$\sum_{i=1}^F b_i \le 10$$

If the total number of holes in all the regions is $H$, we have:

$$F + H = \sum_{i=1}^F b_i \le 10$$

A division of the surface into $F$ regions with a total of $H$ holes can be converted into a division into $F$ simply connected regions by adding $H$ additional edges, without changing the number of vertices (e.g. an annulus can be converted into a disk by adding one edge). Counting these $H$ supplementary edges in addition to the $E$ edges of the graph, we have the Euler characteristic for an orientable surface of genus $g$:

$$V - (E+H) + F = 24 - 36 + F - H = 2 - 2g$$ $$g = 7 - \frac{1}{2}(F-H)$$

But we have:

$$F-H = F+H-2H \le 10-2H$$ $$g \ge 2+H$$

So the genus of the surface must be at least 2, and $g=2$ is only possible when $H=0$ and the surface is divided into $F=10$ simply connected regions.

There is also a nice, symmetrical embedding of this graph into a surface of genus 3:

Dissection of McGee graph into 8 nonagons

The image above shows 8 oriented 9-gons, arranged so that pairs of oppositely-oriented edges from different 9-gons form the edges of the McGee graph. So the Euler characteristic of the oriented surface in which the graph is embedded here is $\chi=24-36+8=-4$, and its genus is $g=3$.

Any dihedral symmetry of the original planar embedding of the graph just permutes these eight 9-gons among themselves. The other graph automorphisms give different 9-gons on the planar embedding, for example:

Dissection of McGee graph into 8 different nonagons

The Riemann surface for the genus 3 embedding looks like this:

Riemann surface of genus 3 from McGee graph

where edges and faces with the same numbers should be identified. The complete symmetry group of this surface is the 16-element dihedral group, with the orientation-preserving symmetries giving an 8-element cyclic subgroup.

$\endgroup$
  • $\begingroup$ Does this embedding preserve some of the symmetry of the graph? $\endgroup$ – Will Sawin Sep 17 '15 at 13:17
  • $\begingroup$ @Will Sawin: I don't understand exactly what you're asking. Does it entail putting a metric on the surface, or are you talking about something else? $\endgroup$ – Greg Egan Sep 17 '15 at 13:33
  • $\begingroup$ I just want to know if there are automorphisms of the surface that send the graph to the graph and act on the graph as one of the 32 automorphisms in its automorphism group. Automorphisms in the topological category are fine. $\endgroup$ – Will Sawin Sep 17 '15 at 14:25
  • 2
    $\begingroup$ I've done some computer calculations to rule out any genus 2 embedding, so the genus of the graph appears to be exactly 3. $\endgroup$ – Greg Egan Sep 18 '15 at 7:47
  • 2
    $\begingroup$ I've now dealt with the possibility that the embedding of the graph divides the surface into regions that might not all be simply connected. The result still holds: the genus of the surface must be at least 3. $\endgroup$ – Greg Egan Sep 20 '15 at 4:22
9
$\begingroup$

This is not an answer, only an illustration. I tried to find a maximally symmetric embedding into 3-space.

It might be viewed as an embedding into a solid torus, with two disjoint 8-cycles on the surface and 8 vertices in four $\boldsymbol\rangle\!\!\!\boldsymbol-\!\!\!\boldsymbol\langle$-like shapes inside the torus.

Motion realizes an automorphism of order 8 (image of the embedding coincides with itself after every $\frac\pi2$-turn; after $2\pi$ one gets a nontrivial involution).

$\ \hskip8em \ $enter image description here

Many thanks to Simon Rose for immediately noticing that my first attempt was obviously rubbish.

$\endgroup$
  • $\begingroup$ That can't be the same graph; it has several cycles of length 4. $\endgroup$ – Simon Rose Sep 16 '15 at 10:44
  • $\begingroup$ Oops you are right $\endgroup$ – მამუკა ჯიბლაძე Sep 16 '15 at 10:47
  • $\begingroup$ I will stop this for a while :D $\endgroup$ – მამუკა ჯიბლაძე Sep 16 '15 at 10:47
  • $\begingroup$ Corrected (four days ago actually, it just occurred to me that I should say it here) $\endgroup$ – მამუკა ჯიბლაძე Sep 20 '15 at 6:20
  • 2
    $\begingroup$ მამუკა ჯიბლაძე - I'm trying to send you an email to ask if I can use your animation on blog, crediting you. When I send email to mamuka.jibladze@rmi.ge or jib@rmi.acnet.ge, it bounces back to me. $\endgroup$ – John Baez Oct 10 '16 at 20:30
8
$\begingroup$

Thanks to Gordon Royle's help, Greg Egan and I were able to work out some of the algebraic structures related to the McGee graph. I explained them here:

$\endgroup$
  • $\begingroup$ Thanks for the link, very interesting work. Is genus of this graph known? Or generally any nice non-self-intersecting embeddings in some surface? $\endgroup$ – მამუკა ჯიბლაძე Sep 15 '15 at 9:02
  • $\begingroup$ Wikipedia says "The McGee graph requires at least eight crossings in any drawing of it in the plane. It is one of five non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these five graphs is the generalized Petersen graph G(12,5), also known as the Nauru graph." Does this tell you the genus of the graph? Maybe there's a nice Riemann surface you can draw the McGee graph on, with the McGee symmetry group $\mathrm{GA}(1,\mathbb{Z}/8)$ acting as conformal transformations. $\endgroup$ – John Baez Sep 16 '15 at 2:18
  • $\begingroup$ Seems like Nauru graph can be very nicely drawn on a torus but what does this tell about the McGee graph? $\endgroup$ – მამუკა ჯიბლაძე Sep 16 '15 at 5:00
3
$\begingroup$

certainly Sage(math) can easily compute the structure of this group:

sage: g=graphs.McGeeGraph()
sage: a=g.automorphism_group()    
sage: a.structure_description()
'(C2 x D4) : C2'

(Sage makes an unusual choice to denote the dihedral group $D_{2k}$ of order $2k$ as $D_k$...)

$\endgroup$
  • $\begingroup$ [edited just to fix a transparent typo] $\endgroup$ – Noam D. Elkies Sep 18 '15 at 4:08
  • $\begingroup$ That is a very odd choice because as far as I can tell, the structure_description() command is pushed off to GAP, which uses $D_{2k}$. $\endgroup$ – Gordon Royle Sep 18 '15 at 5:21
  • $\begingroup$ if k is odd it becomes truly odd :) Well, there are books making this choice, although no modern finite group theory papers do so, IMHO. $\endgroup$ – Dima Pasechnik Sep 18 '15 at 5:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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