Baxter permutations and plane bipolar orientations |
| |
| Affiliation: | 1. LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence, France;2. Dept. Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, V5A 1S6, Canada;1. LaBRI, Université de Bordeaux, CNRS, 351 cours de la Libération, 33405 Talence, France;2. Université Libre de Bruxelles (ULB), Département de Mathématique, Boulevard du Triomphe, B-1050 Bruxelles, Belgium;3. University of Strathclyde, Department of Computer and Information Sciences, 16 Richmond Street, Glasgow G1 1XQ, Scotland, United Kingdom;4. Stanford University, Department of Mathematics, building 380, Stanford, CA 94305, USA;1. Stanford University, Department of Mathematics, building 380, Stanford, CA 94305, USA;2. University of California, San Diego, Department of Mathematics, 9500 Gilman Dr. #0112, San Diego, CA 92093, USA;1. Fak. für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria;2. LIAFA, Université Paris Diderot, Case 7014, F-75205 Paris Cedex 13, France |
| |
| Abstract: | 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 into natural parameters of orientations, and has remarkable symmetry properties. By specialising it to Baxter permutations avoiding the pattern 3142, we obtain a bijection with non-separable planar maps, which had been described only in an implicit recursive manner so far (up to simple symmetries). A further specialization yields a bijection between permutations avoiding 3142 and 2413 and series-parallel maps. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
