Cayley graph of $A_5$ with generators $(1,2,3,4,5),(1,4,3,2,5)$ 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.
 A: 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

*

*icosidodecadodecahedron , with Euler characteristic -16
and


*rhombidodecadodecahedron  with Euler characteristic -6.
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\}$:

A: 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.
A: 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
A: 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
