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 $n$th Baxter number $b(n)$, which can be defined by a linear recurrence relation with polynomial coefficients. Equivalently, the associated generating function ${\sum }_{n}b(n)t^n$ 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 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.

arXiv comment64 pages. Special issue of the Séminaire Lotharingien de Combinatoire, dedicated to Christian Krattenthaler's 60th birthday

References in corpus (18)

• The topological structure of scaling limits of large planar maps
• Walks with small steps in the quarter plane
• Random walks in cones
• Bijections for Baxter Families and Related Objects
• Local limit of labeled trees and expected volume growth in a random quadrangulation
• Computing periods of rational integrals
• The fractal dimension of Liouville quantum gravity: universality, monotonicity, and bounds
• Intervals in the greedy Tamari posets
• Counting quadrant walks via Tutte's invariant method
• Multiple binomial sums
• Random geometry on the sphere
• The representation of the symmetric group on m-Tamari intervals
• The two uniform infinite quadrangulations of the plane have the same law
• Random walks in the quarter plane, discrete harmonic functions and conformal mappings
• Counting quadrant walks via Tutte's invariant method (extended abstract)
• Bijective counting of plane bipolar orientations and Schnyder woods
• A bijection between certain quarter plane walks and Motzkin paths
• On the three-rowed skew standard Young tableaux

Cited by in corpus (3)

• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• The skew Brownian permuton: a new universality class for random constrained permutations
• Constructing discrete harmonic functions in wedges