Baxter Permutations and Plane Bipolar Orientations
Séminaire lotharingien de combinatoire, 61A (2009-2011)
Citer cet article
Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website
We present a simple bijection between Baxter permutations of size n and plane bipolar orientations with n edges. This bijection translates several classical parameters of permutations (number of ascents, right-to-left maxima, left-to-right minima ...) into natural parameters of plane bipolar orientations (number of vertices, degree of the sink, degree of the source ...), and has remarkable symmetry properties. % By specializing it to Baxter permutations avoiding the pattern 2413, we obtain a bijection with non-separable planar maps. A further specialization yields a bijection between permutations avoiding 2413 and 3142 and series-parallel maps.