hal-00669896, version 3

A simple model of trees for unicellular maps

Guillaume Chapuy (, ) ¹, Valentin Feray () ², Eric Fusy ³

• 1:  Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA)
• http://www.liafa.jussieu.fr/
  CNRS : UMR7089 – Université Paris VII - Paris Diderot 2, place Jussieu, Case 7014, 75251 Paris Cedex 05 - Tél: +33(0)1.44.27.68.45 - Fax: +33(0)1.44.27.68.49 France
• 2:  Laboratoire Bordelais de Recherche en Informatique (LaBRI)
• http://www.labri.fr
  CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II Domaine Universitaire 351, cours de la Libération 33405 Talence Cedex France
• 3:  Laboratoire d'informatique de l'école polytechnique (LIX)
• http://www.lix.polytechnique.fr/
  CNRS : UMR7161 – Polytechnique - X Route de Saclay 91128 PALAISEAU CEDEX France

Bibliographic reference

• Type of document: Documents without publication reference (Preprint)
• Subject: Mathematics/Combinatorics
• Title: A simple model of trees for unicellular maps
• Abstract: We consider unicellular maps, or polygon gluings, of fixed genus. A few years ago the first author gave a recursive bijection transforming unicellular maps into trees, explaining the presence of Catalan numbers in counting formulas for these objects. In this paper, we give another bijection that explicitly describes the ''recursive part'' of the first bijection. As a result we obtain a very simple description of unicellular maps as pairs made by a plane tree and a permutation-like structure. All the previously known formulas follow as an immediate corollary or easy exercise, thus giving a bijective proof for each of them, in a unified way. For some of these formulas, this is the first bijective proof, e.g. the Harer-Zagier recurrence formula, or the Lehman-Walsh/Goupil-Schaeffer formulas. Thanks to previous work of the second author this also leads us to a new expression for Stanley character polynomials, which evaluate irreducible characters of the symmetric group.
• Fulltext language: English
• Comment: v3: short version, 11 pages (extended abstract for FPSAC'12).
• European project:

  Cordis number	208471
  Acronyme	EXPLOREMAPS
  Title	Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.
  Funded by	ERC
  Start date	2008-07-01
  End date	2013-06-30
  Call identifier	ERC-2007-StG

Attached file list to this document: 

TEX

C-tree.eps(63.3 KB)

Remy.eps(31.8 KB)

map-trisection.eps(109.7 KB)

map-trisectionC.eps(94.6 KB)

maps1-finalFPSAC-pourHAL.bbl(2.6 KB)

maps1-finalFPSAC-pourHAL.tex(65.1 KB)

PDF

maps1-finalFPSAC-pourHAL.pdf(221.7 KB)

PS

maps1-finalFPSAC-pourHAL.ps(877.4 KB)

• hal-00669896, version 3
• http://hal.archives-ouvertes.fr/hal-00669896
• oai:hal.archives-ouvertes.fr:hal-00669896
• From: Guillaume Chapuy <>
• Submitted on: Tuesday, 31 July 2012 08:28:00
• Updated on: Tuesday, 31 July 2012 08:46:48