Paper Info
Title
Bijective counting of plane bipolar orientations and Schnyder woods
Abstract
A bijection @F 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 Baxter for the number @Q"i"j of plane bipolar orientations with i non-polar vertices and j inner faces: @Q"i"j=2(i+j)!(i+j+1)!(i+j+2)!i!(i+1)!(i+2)!j!(j+1)!(j+2)!. In addition, it is shown that @F specializes into the bijection of Bernardi and Bonichon between Schnyder woods and non-crossing pairs of Dyck words. This is the extended and revised journal version of a conference paper with the title ''Bijective counting of plane bipolar orientations'', which appeared in Electr. Notes in Discr. Math. pp. 283-287 (Proceedings of Eurocomb'07, 11-15 September 2007, Sevilla).
Year
DOI
Venue
2009
10.1016/j.ejc.2009.03.001
Eur. J. Comb.
Field
DocType
Volume
Discrete mathematics,Combinatorics,Bijection,Lattice (order),Vertex (geometry),Combinatorial proof,Mathematics
Journal
30
Issue
ISSN
Citations 
7
0195-6698
6
PageRank 
References 
Authors
0.51
11
3
Name
Order
Citations
PageRank
Éric Fusy119821.95
Dominique Poulalhon21279.73
Gilles Schaeffer342344.82