Random 2-cell embeddings of multistars

03/08/2021
by   Jesse Campion Loth, et al.
0

By using permutation representations of maps, one obtains a bijection between all maps whose underlying graph is isomorphic to a graph G and products of permutations of given cycle types. By using statistics on cycle distributions in products of permutations, one can derive information on the set of all 2-cell embeddings of G. In this paper, we study multistars – loopless multigraphs in which there is a vertex incident with all the edges. The well known genus distribution of the two-vertex multistar, also known as a dipole, can be used to determine the expected genus of the dipole. We then use a result of Stanley to show that, in general, the expected genus of every multistar with n nonleaf edges lies in an interval of length 2/(n+1) centered at the expected genus of an n-edge dipole. As an application, we show that the face distribution of the multistar is the same as the face distribution gained when adding a new vertex to a 2-cell embedded graph, and use this to obtain a general upper bound for the expected number of faces in random embeddings of graphs.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset