Random Cayley Maps for Groups Generated by Involutions

Let Γ be a finite group and let Δ be a generating set for Γ. A Cayley map associated with Γ and Δ is an orientable 2-cell imbedding of the Cayley graph GΔ(Γ) such that the rotation of arcs emanating from each vertex is determined by a unique cyclic permutation of generators and their inverses. A probability model for the set of all Cayley maps for a fixed group and generating set, where the distribution is uniform, is investigated in the special case when the generating set contains only elements of order 2. The Cayley genus, maximum Cayley genus, and average Cayley genus are the minimum, maximum, and expected value of the genus random variable associated with this probability model. These parameters are determined for abelian groups, symmetric groups, and dihedral groups (with certain prescribed generating sets). Using the dihedral groups, it is shown that the difference between two consecutive values in the Cayley genus distribution may be arbitrarily large. Further, for each group and its prescribed generating set, the likelihood that a given Cayley map is symmetrical is determined.