Our methods are a mixture of probabilistic and algebraic. We make use of recent bounds [1]} on the average genus of a randomly chosen embedding of \(K_n\) , and techniques for calculating this average genus in general [2]}. We also make use of some algebraic machinery: representations of the symmetric group. We prove a new, simple bound for hook-shaped characters, and combine it with a general technique for calculating differences between probability distributions [3]}[4]}. The representation theory is self-contained in Section . The reader who is mainly interested in conjugacy class products may refer to this section, while the reader more interested in graph theory may skip this section without any large loss of understanding.
