20
$\begingroup$

The Cayley graph of $A_5$ with two generators of order 5 seems rather complicated. What is its graph genus (orientable or non-orientable)?

  • The best I could get by trial and error is an embedding without crossings on a sphere with 10 crosscaps.

  • Running the following in Sage works in theory, but takes too long: A5 = groups.permutation.Alternating(5) S = [(1,2,3,4,5),(1,4,3,2,5)] d = A5.cayley_graph(generators=S) bt = d.to_undirected() bt.genus()

  • In Sage we can also use JSMol to get a not-so-helpful view of the graph.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ The group $A_5$ has two connected non-isomorphic Cayley graphs with the mentioned properties, namely $\mathrm{Cay}(A_5,\{(1\ 2\ 3\ 4\ 5), (1\ 2\ 3\ 5\ 4)\})$ and $\mathrm{Cay}(A_5,\{(1\ 2\ 3\ 4\ 5), (1\ 2\ 4\ 5\ 3)\})$. $\endgroup$
    – M. Farrokhi D. G.
    Jul 3, 2018 at 11:14
  • 3
    $\begingroup$ As we know, $A_5$ has two conjugacy classes of $5$-cycles. The two non-isomorphic Cayley graphs $\mathrm{Cay}(A_5,\{\pi,\tau\})$ arises from the fact that $\pi$ and $\tau$ belong to the same conjugacy class or not. One can check that the girth of $\mathrm{Cay}(A_5,\{\pi,\tau\})$ is $5$ if $\pi$ and $\tau$ belong to the same conjugacy class, and it is $4$ otherwise. $\endgroup$
    – M. Farrokhi D. G.
    Jul 4, 2018 at 6:09
  • $\begingroup$ @M.FarrokhiD.G. Thanks very much. I suppose it's not clear whether those two have the same genus then. $\endgroup$
    – Bjørn Kjos-Hanssen
    Jul 4, 2018 at 6:39
  • 1
    $\begingroup$ The question about Bring's sextic might hold the key... $\endgroup$
    – მამუკა ჯიბლაძე
    Mar 20, 2021 at 21:09
  • $\begingroup$ @მამუკაჯიბლაძე Really? The plot thickens... $\endgroup$
    – Bjørn Kjos-Hanssen
    Mar 21, 2021 at 22:18

4 Answers 4

Reset to default
5
+50
$\begingroup$

I don't know exact genus. I suspect it is 4 but do not have a proof. So I am making this community wiki, maybe somebody can supply this information.

The generating cycles $p$ and $q$ satisfy $(pq)^3=(p^{-1}q)^2=1$, so the Cayley graph can be obtained as a quotient of a tiling of the hyperbolic plane in at least two ways. One may take either (click on images if you want to enlarge)

  • the quotient of the pentahexagonal tiling which makes succession of vertices along each line periodic with period 4, or

  • the quotient of the tetrapentagonal tiling which makes succession of vertices along each line periodic with period 6.

These give respectively the

The first, if orientable, has genus 9 and if not, 18; the second, if orientable, has genus 4 and if not, 8.

As Bjørn Kjos-Hanssen explains in a comment below, the rhombidodecadodecahedron is actually orientable, so this gives upper bound 4 on the orientable genus.

Further info:

  • Wikipedia pages link to some Python code but I never tried it myself
  • Jeff Weeks' Kaleidotile can be used to generate the tilings above
  • Jonathan Bowers states that if the verf (the set of vertices adjacent to a fixed vertex) is a trapezoid then the polyhedron is orientable. In particular "raded" (rhombidodecadodecahedron) is orientable.

Here is one possible gluing scheme of the tetrapentagonal tiling giving a surface of genus 4: After the gluing one gets three vertices 0, 1, 2, and ten edges - X,Y,Z,T,U oriented from 0 to 1 and a,b,c,d,e oriented from 0 to 2. Choosing 0 for basepoint, this gives ten loops $\alpha_0=ad^{-1}$, $\alpha_1=de^{-1}$, $\alpha_2=eb^{-1}$, $\alpha_3=bc^{-1}$, $\alpha_4=ca^{-1}$ and $\beta_0=XU^{-1}$, $\beta_1=UT^{-1}$, $\beta_2=TZ^{-1}$, $\beta_3=ZY^{-1}$, $\beta_4=YX^{-1}$ generating the fundamental group, with relations $\alpha_0\alpha_1\alpha_2\alpha_3\alpha_4=\beta_0\beta_1\beta_2\beta_3\beta_4=\alpha_0\beta_0\alpha_3\beta_2\alpha_1\beta_4\alpha_4\beta_1\alpha_2\beta_3=1$. Or, eliminating, say, $\alpha_0$ and $\beta_0$ from the first two relations, one is left with 8 generators and single relation $\alpha_3\beta_2\alpha_1\beta_4\alpha_4\beta_1\alpha_2\beta_3=\beta_1\beta_2\beta_3\beta_4\alpha_1\alpha_2\alpha_3\alpha_4$. So the first homology group is $\mathbb Z^8$, as it should be for a genus 4 surface.

One more gluing scheme on a genus 4 surface, constructed using the regular map $\mathrm S4:\{5,5\}$:

enter image description here

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ @BjørnKjos-Hanssen These two relations suffice (checked it with GAP). As for kaleidotile, the two pictures, with three colors each, are obtained with 3,5,5 and 2,5,5 respectively, sliding the point to the middle of the lower edge of the triangle. $\endgroup$
    – მამუკა ჯიბლაძე
    Dec 30, 2019 at 7:07
  • $\begingroup$ @BjørnKjos-Hanssen Thanks for the bounty! Inspired by it, I found on Wikipedia the polyhedra corresponding to these quotient tesselations. I still do not know the exact genus, though. $\endgroup$
    – მამუკა ჯიბლაძე
    Jan 1, 2020 at 19:23
  • $\begingroup$ @BjørnKjos-Hanssen Unfortunately I cannot figure out whether the rhombidodecadodecahedron is orientable. If it is this will give upper bound 4 on the oriented genus. If not, this will give upper bound 8 on the non-oriented genus. $\endgroup$
    – მამუკა ჯიბლაძე
    Jan 1, 2020 at 21:10
  • $\begingroup$ @BjørnKjos-Hanssen Great! In his nomenclature it is "raded". So then the oriented genus is at most 4. $\endgroup$
    – მამუკა ჯიბლაძე
    Jan 1, 2020 at 21:36
  • 1
    $\begingroup$ @BjørnKjos-Hanssen Well in a sense it is itself such a representation. You mean a map on a sphere with 4 handles with no self-intersections? $\endgroup$
    – მამუკა ჯიბლაძე
    Jan 1, 2020 at 21:56
2
$\begingroup$

You can also get this graph with Ed Pegg's demo of Cayley Graphs at Wolfram demonstrations, by taking the bottom slider to permutation 94 of 120.enter image description here

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ This post, while useful in some ways (and not really convertible to a comment), has been flagged "not an answer". Maybe, as a compromise, make it CW? $\endgroup$
    – Todd Trimble ♦
    Dec 27, 2019 at 22:46
  • $\begingroup$ @ToddTrimble it's a step in the right direction so I'd like to award the bounty... maybe undo the community wiki? $\endgroup$
    – Bjørn Kjos-Hanssen
    Dec 28, 2019 at 0:45
  • 2
    $\begingroup$ @BjørnKjos-Hanssen You'd be in the best position to judge which post best answers your question or helps you the most, so I defer to you. $\endgroup$
    – Todd Trimble ♦
    Dec 28, 2019 at 1:03
2
$\begingroup$

According to Sagemath documentation, the time complexity of their algorithm is $$ \mathcal{O}\left(|V| \prod_{v \in V} (d(v) - 1)!\right). $$ (Note that in this instance this evaluates to $6^{60}$.)

However, quick google search reveals that approach via integer linear programming or SAT solvers might be viable for this particular case. I suggest you contact the authors of the following articles:

Stronger ILPs for the Graph Genus Problem, 27th Annual European Symposium on Algorithms (ESA 2019)

A Practical Method for the Minimum Genus of a Graph: Models and Experiments, International Symposium on Experimental Algorithms, SEA 2016: Experimental Algorithms, pp 75-88

Improve this answer
$\endgroup$
1
1
$\begingroup$

There are computer programs to try, although I don't know how fast they are (the problem at hand is NP-complete).

E.g. Sagemath has an implementation of genus computation: http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/genus.html

Improve this answer
$\endgroup$
8
  • $\begingroup$ Have you tried it on your graphs? $\endgroup$
    – Dima Pasechnik
    Jul 3, 2018 at 15:26
  • 1
    $\begingroup$ I imagine it gets slow as the genus gets high, but for low genus it ought to be fast... $\endgroup$
    – Dima Pasechnik
    Jul 3, 2018 at 15:28
  • $\begingroup$ @BjørnKjos-Hanssen Also, documentation is horrible. $\endgroup$
    – Igor Rivin
    Jul 3, 2018 at 23:48
  • 6
    $\begingroup$ we always appreciate suggestions on how to improve Sagemath :-) $\endgroup$
    – Dima Pasechnik
    Jul 4, 2018 at 4:55
  • 1
    $\begingroup$ it makes sense to specify which groups your permutations are coming from, i.e. as follows: sage: p=PermutationGroupElement('(1,2)(3,4)',parent=A5) sage: p in bt.vertices() True Does this cover your needs? $\endgroup$
    – Dima Pasechnik
    Jul 4, 2018 at 6:56

Your Answer

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