A bijection for triangulations, quadrangulations, pentagulations, etc
| Autor: | Olivier Bernardi, íric Fusy |
|---|---|
| Přispěvatelé: | Massachusetts Institute of Technology (MIT), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), European Project: 208471,EC:FP7:ERC,ERC-2007-StG,EXPLOREMAPS(2008) |
| Rok vydání: | 2010 |
| Předmět: |
Counting
Unified bijections 0102 computer and information sciences Mathematical proof 01 natural sciences Theoretical Computer Science Combinatorics symbols.namesake Computer Science::Discrete Mathematics Mathematics::Category Theory [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics 0101 mathematics Mathematics Maps with boundaries Discrete mathematics Mathematics::Combinatorics 010102 general mathematics d-Angulations Graph Planar graph Computational Theory and Mathematics 010201 computation theory & mathematics Bijection symbols Master bijection Combinatorics (math.CO) Bijection injection and surjection |
| Zdroj: | Journal of Combinatorial Theory, Series A Journal of Combinatorial Theory, Series A, 2012, 119 (1), pp.218-244 |
| ISSN: | 0097-3165 1096-0899 |
| DOI: | 10.48550/arxiv.1007.1292 |
| Popis: | International audience; A $d$-angulation is a planar map with faces of degree $d$. We present for each integer $d\geq 3$ a bijection between the class of $d$-angulations of girth~$d$ (i.e., with no cycle of length less than $d$) and a class of decorated plane trees. Each of the bijections is obtained by specializing a ''master bijection'' which extends an earlier construction of the first author. Our construction unifies known bijections by Fusy, Poulalhon and Schaeffer for triangulations ($d=3$) and by Schaeffer for quadrangulations ($d=4$). For $d\geq 5$, both the bijections and the enumerative results are new. We also extend our bijections so as to enumerate \emph{$p$-gonal $d$-angulations} ($d$-angulations with a simple boundary of length $p$) of girth $d$. We thereby recover bijectively the results of Brown for simple $p$-gonal triangulations and simple $2p$-gonal quadrangulations and establish new results for $d\geq 5$. A key ingredient in our proofs is a class of orientations characterizing $d$-angulations of girth $d$. Earlier results by Schnyder and by De Fraysseix and Ossona de Mendez showed that simple triangulations and simple quadrangulations are characterized by the existence of orientations having respectively indegree 3 and 2 at each inner vertex. We extend this characterization by showing that a $d$-angulation has girth $d$ if and only if the graph obtained by duplicating each edge $d-2$ times admits an orientation having indegree $d$ at each inner vertex. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect