Séminaire Lotharingien de Combinatoire, B81l (2020), 63 pp.
Mireille Bousquet-Mélou, Éric Fusy and Kilian Raschel
Plane Bipolar Orientations and Quadrant Walks
Abstract.
Bipolar orientations of planar maps have recently attracted some interest in
combinatorics, probability theory and theoretical physics. Plane bipolar
orientations with n edges are known to be counted by the nth
Baxter number b(n), which can be defined by a linear recurrence
relation with polynomial coefficients. Equivalently, the associated generating function
\sumn b(n) tn is D-finite. In this
paper, we address a much refined enumeration problem, where we record
for every r the number of faces of degree r. When these degrees
are bounded, {we show that} the associated generating function is given as the constant term of a
multivariate rational series, and thus is still D-finite.
We also provide detailed asymptotic estimates for the corresponding
numbers.
The methods used earlier to count all plane bipolar orientations, regardless of their
face degrees, do not generalize easily to record face
degrees. Instead, we start from a recent bijection, due to Kenyon \emph{et
al.}, that sends bipolar orientations onto certain lattice walks confined to
the first quadrant. Due to this bijection, the study of bipolar
orientations meets the study of walks confined to a cone, which has
been extremely active in the past 15 years. Some of our proofs rely on
recent developments in this field, while others are purely
bijective. Our asymptotic results also involve probabilistic arguments.
Received: May 10, 2019.
Revised: May 1, 2020.
Accepted: June 27, 2020.
The following versions are available: