The University of Michigan Combinatorics Seminar


Abstract 

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 HarerZagier formula, obtained in joint work with Ian Goulden. The proof is done via the bijective enumeration of a set of "pairedcircuits" (which will be introduced in the talk, and the enumeration of which is equivalent to the HarerZagier formula). 