Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. A unified bijective ...
Conference paper

A unified bijective method for maps: application to two classes with boundaries

Olivier Bernardi ORCID (1), Eric Fusy (2)
(1) Department of Mathematics [MIT]
(2) Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
Proceedings
DOI
10.46298/dmtcs.2869
License
https://about.hal.science/hal-authorisation-v1
European Commission
208471
Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.
Indicators
610
Views
428
Downloads

A unified bijective method for maps: application to two classes with boundaries

Olivier Bernardi ORCID (1), Eric Fusy (2)
(1) Department of Mathematics [MIT]
(2) Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract
English
Based on a construction of the first author, we present a general bijection between certain decorated plane trees and certain orientations of planar maps with no counterclockwise circuit. Many natural classes of maps (e.g. Eulerian maps, simple triangulations,...) are in bijection with a subset of these orientations, and our construction restricts in a simple way on the subset. This gives a general bijective strategy for classes of maps. As a non-trivial application of our method we give the first bijective proofs for counting (rooted) simple triangulations and quadrangulations with a boundary of arbitrary size, recovering enumeration results found by Brown using Tutte's recursive method.
French
En nous appuyant sur une construction du premier auteur, nous donnons une bijection générale entre certains arbres décorés et certaines orientations de cartes planaires sans cycle direct. De nombreuses classes de cartes (par exemple les eulériennes, les triangulations) sont en bijection avec un sous-ensemble de ces orientations, et notre construction se spécialise de manière simple sur le sous-ensemble. Cela donne un cadre bijectif général pour traiter les familles de cartes. Comme application non-triviale de notre méthode nous donnons les premières preuves bijectives pour l'énumération des triangulations et quadrangulations simples (enracinées) ayant un bord de taille arbitraire, et retrouvons ainsi des formules de comptage trouvées par Brown en utilisant la méthode récursive de Tutte.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Triangulation
  • quadrangulation
  • maps with boundaries
  • mobiles
  • bijection
  • counting
Preview
Loading PDF preview...