The University of Michigan Combinatorics Seminar
Fall 2005
October 21, 4:10-5:00, 3866 East Hall



A direct bijection for the Harer-Zagier formula

Alexandru Nica

University of Waterloo


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 Sn (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).