Graph embeddings and permutation products

For some A, B ⊆ Sn, determining the cycle structure of the multiset AB = {a · b : a ∈ A, b ∈ B} is a problem arising in several different areas of mathematics. When the sets of permutations A and B are conjugacy classes of the symmetric group, then the problem is linked with representation theory, as it tells us about the structure of the centre of the group algebra. When A and B are certain subsets of conjugacy classes, then the cycle structure of AB tells us the number of embeddings of some graph on each oriented surface. Due to the difficulty of the problem, exact results are only known for nicely structured sets A and B. Therefore many previous approaches to problems of this type focus on the asymptotic cycle structure of AB, and the average number of cycles in AB. Combinatorial techniques using maps are often used to study these problems, as well as more algebraic methods using character theory. We start by studying products of conjugacy classes of the symmetric group. We show two asymptotic results: That (Cλ)m tends to the uniform distribution as m → ∞, and that CαCβ tends to the uniform distribution as the size of the symmetric group tends to infinity, over any sequences of conjugacy classes with sufficiently large cycles. We then use maps to partially explain these results combinatorially, showing that the average number of cycles in any CαCβ is very close to the nth harmonic number, as long as α and β have no parts of size one. We then apply these results and techniques to problems from topological graph theory. In particular, we study the average genus, or equivalently the average number of faces, over all the embeddings of a fixed graph. We give a bound on this average for all graphs, and an improved bound for the complete graph. We also give bounds for several models of random graph. Finally, we bring together all the results of the thesis to prove a limiting uniformity for the number of cycles across all of the embeddings of the complete graph. We then use maps to partially explain these results combinatorially, showing that the average number of cycles in any CαCβ is very close to the nth harmonic number, as long as α and β have no parts of size one. We then apply these results and techniques to problems from topological graph theory. In particular, we study the average genus, or equivalently the average number of faces, over all the embeddings of a fixed graph. We give a bound on this average for all graphs, and an improved bound for the complete graph. We also give bounds for several models of random graph. Finally, we bring together all the results of the thesis to prove a limiting uniformity for the number of cycles across all of the embeddings of the complete graph.