Bijective counting of plane bipolar orientations and Schnyder woods

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

A bijection $Φ$ is presented between plane bipolar orientations with prescribed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with prescribed extremities. This yields a combinatorial proof of the following formula due to R. Baxter for the number $Θ_{ij}$ of plane bipolar orientations with $i$ non-polar vertices and $j$ inner faces: $Θ_{ij}=2\frac{(i+j)!(i+j+1)!(i+j+2)!}{i!(i+1)!(i+2)!j!(j+1)!(j+2)!}$. In addition, it is shown that $Φ$ specializes into the bijection of Bernardi and Bonichon between Schnyder woods and non-crossing pairs of Dyck words.
An extended abstract describing the bijection without proofs has appeared in the proceedings of Eurocomb'07

Keywords

Combinatorics, 05A15

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/223783

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0803.0400
 http://arxiv.org/abs/0803.0400

Collections

arXiv