A direct bijection for the Harer-Zagier formula

In 1986, Harer and Zagier gave an explicit formula for the cycle distribution of γ⋅μ, where γ is a long cycle and μ is an involution without fixed points in the symmetric group S_n (for n even). The original proof found by Harer and Zagier for this formula uses Gaussian random matrices. Several other proofs were given after that; but (despite the elementary flavour of the formula) the proofs are not easy, and usually move out of the realm of enumerative combinatorics. In this talk I will describe a direct combinatorial proof of the Harer-Zagier formula, obtained in joint work with Ian Goulden. The proof is done via the bijective enumeration of a set of "paired-circuits" (which will be introduced in the talk, and the enumeration of which is equivalent to the Harer-Zagier formula).