On the enumeration of plane bipolar posets and transversal structures

DOI10.1016/J.EJC.2023.103870MaRDI QIDQ6146499zbMATH OpenOpenAlexFDO

Authors Éric Fusy, Erkan Narmanli, Gilles Schaeffer

Publication date 5 February 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.06955

zbMATH Keywords

algebraic generating functionconstrained orientations

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Combinatorics of partially ordered sets (06A07) Combinatorial probability (60C05) Sums of independent random variables; random walks (60G50) Stochastic (Schramm-)Loewner evolution (SLE) (60J67)

Abstract: We show that plane bipolar posets (i.e., plane bipolar orientations with no transitive edge) and transversal structures can be set in correspondence to certain (weighted) models of quadrant walks, via suitable specializations of a bijection due to Kenyon, Miller, Sheffield and Wilson. We then derive exact and asymptotic counting results. In particular we prove (computationally and then bijectively) that the number of plane bipolar posets on $n+2$ vertices equals the number of plane permutations of size $n$. Regarding transversal structures, for each $vgeq0$ we consider $t_n(v)$ the number of such structures with $n+4$ vertices and weight $v$ per quadrangular inner face (the case $v=0$ corresponds to having only triangular inner faces). We obtain a recurrence to compute $t_n(v)$, and an asymptotic formula that for $v=0$ gives $t_n(0)simc!(27/2{)}^n{n}^{-1-pi/mathrmarccos(7/8)}$ for some $c>0$, which also ensures that the associated generating function is not D-finite.

Recommendations

• Bijective counting of plane bipolar orientations
• Bijective counting of plane bipolar orientations and Schnyder woods
• A bijection for plane graphs and its applications
• Baxter permutations and plane bipolar orientations
• Bijections for Baxter families and related objects

Cites work

• A (4n − 4)-Bit Representation of a Rectangular Drawing or Floorplan
• A Census of Planar Maps
• Almost flat planar diagrams
• Area requirement and symmetry display of planar upward drawings
• Asymptotic enumeration of orientations
• Baxter permutations and plane bipolar orientations
• Bipolar orientations on planar maps and \(\mathrm{SLE}_{12}\)
• Bipolar orientations revisited
• Convex drawings of 3-connected plane graphs
• Counting planar maps, coloured or uncoloured
• Counting surfaces. CRM Aisenstadt chair lectures
• Exact solution of discrete two-dimensional \(R^2\) gravity
• Forest-like permutations
• Generic rectangulations
• Handbook of Enumerative Combinatorics
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 3786844 (Why is no real title available?)
• Intervals in Catalan lattices and realizers of triangulations
• Lattice structures from planar graphs
• New bijective links on planar maps via orientations
• Non-D-finite excursions in the quarter plane
• On Finding the Rectangular Duals of Planar Triangular Graphs
• On the number of tilings of a square by rectangles
• Planar Lattices
• Planar maps
• Random walks in cones
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence
• The fractal dimension of Liouville quantum gravity: universality, monotonicity, and bounds
• The generating function of planar Eulerian orientations
• The permuton limit of strong-Baxter and semi-Baxter permutations is the skew Brownian permuton
• The skew Brownian permuton: A new universality class for random constrained permutations
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• Universal singular exponents in catalytic variable equations

Cited in

(2)

• Rectangulotopes
• Combinatorics of rectangulations: old and new bijections

This page was built for publication: On the enumeration of plane bipolar posets and transversal structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6146499)