Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In a 1986 paper, Harer and Zagier proved the recursion:

$$(n+1)e(g,n)=(4n-2)e(g,n-1)+(2n-1)(n-1)(2n-3)e(g-1,n-2)$$

where e(g,n) is the number of ways of grouping sides $S_1...S_{2n}$ of a 2n-gon into n pairs, such that, after identifying pairs with the corresponding orientation one gets an orientable surface of genus g.

Their proof is really indirect, it involves pages of calculations.

Is there a simple proof of this fact?

share|improve this question
    
So it's actually Zagier and not Zaiger or Zager? –  Stopple Mar 28 '13 at 18:59
add comment

2 Answers

up vote 8 down vote accepted

http://arxiv.org/abs/0712.2448

Gluing of Surfaces with Polygonal Boundaries E. T. Akhmedov, Sh. Shakirov

By pairwise gluing of edges of a polygon, o produces two-dimensional surfaces with handles and boundaries. In this paper, we count the number ${\cal N}_{g,L}(n_1, n_2, n_L)$ of different ways to produce a surfac of given genus $g$ with $L$ polygonal boundaries with given numbers of edges $n_1, n_2, >..., n_L$. Using combinatorial relations between graphs on real two-dimensional surfaces, we derive recursive relations between $\cal N_{g,L}$. We show that Harer-Zagier numbers appear as a particular case of ${\cal N}_{g,L}$ and deriv a new explicit expression for them. Comments: 7 pages, 9 figures

It seems proposes quite elementary proof. The key idea that they found some generalization which is more easy to prove.

share|improve this answer
add comment

How about

Goulden, I. P.; Nica, A. A direct bijection for the Harer-Zagier formula. J. Combin. Theory Ser. A 111 (2005), no. 2, 224–238.

or one of the references therein?

share|improve this answer
3  
I'll just point out the work of Bodo Lass in 2000, which is a quite simple combinatorial proof (in French) cited by Goulden-Nica. His approach was extended in 2011 by Olivier Bernardi. A bijective proof can also be found in the work of Chapuy, Féray & Fusy (2012), building on earlier work of Chapuy. –  Philippe Nadeau Mar 28 '13 at 18:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.