On the number of planar Eulerian orientations
From MaRDI portal
Publication:2400972
DOI10.1016/J.EJC.2017.04.009zbMATH Open1369.05110arXiv1610.09837OpenAlexW2963234681MaRDI QIDQ2400972FDOQ2400972
Authors: Nicolas Bonichon, Mireille Bousquet-Mélou, Paul Dorbec, Claire Pennarun 
Publication date: 31 August 2017
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: The number of planar Eulerian maps with n edges is well-known to have a simple expression. But what is the number of planar Eulerian orientations with n edges? This problem appears to be difficult. To approach it, we define and count families of subsets and supersets of planar Eulerian orientations, indexed by an integer k, that converge to the set of all planar Eulerian orientations as k increases. The generating functions of our subsets can be characterized by systems of polynomial equations, and are thus algebraic. The generating functions of our supersets are characterized by polynomial systems involving divided differences, as often occurs in map enumeration. We prove that these series are algebraic as well. We obtain in this way lower and upper bounds on the growth rate of planar Eulerian orientations, which appears to be around 12.5.
Full work available at URL: https://arxiv.org/abs/1610.09837
Recommendations
Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Enumeration in graph theory (05C30)
Cites Work
- GFUN
- Analytic combinatorics
- A course in combinatorics.
- Title not available (Why is that?)
- On the Enumeration of Tree-Rooted Maps
- A Census of Planar Maps
- Lattice structures from planar graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random self-avoiding walks on one-dimensional lattices
- A Procedure for Improving the Upper Bound for the Number of n-Ominoes
- Exact solution of the six-vertex model on a random lattice.
- Title not available (Why is that?)
- Random geometry on the sphere
- Optimal coding and sampling of triangulations
- Transversal structures on triangulations: A combinatorial study and straight-line drawings
- Polynomial equations with one catalytic variable, algebraic series and map enumeration
- Counting colored planar maps: algebraicity results
- On the existence of square roots in certain rings of power series
- Counting polyominoes on twisted cylinders
- General Néron desingularization and approximation
- On the enumeration of planar maps
- Bijections for Baxter families and related objects
- Baxter permutations and plane bipolar orientations
- Universal exponents and tail estimates in the enumeration of planar maps
- Enumeration of planar constellations
- Counting colored random triangulations
- Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
- Title not available (Why is that?)
- Succinct representations of planar maps
- Algebraic approximants: a new method of series analysis
- Intervals in Catalan lattices and realizers of triangulations
- Blocked edges on Eulerian maps and mobiles: application to spanning trees, hard particles and the Ising model
- Algorithms for combinatorial structures: well-founded systems and Newton iterations
- The Potts-\(q\) random matrix model: Loop equations, critical exponents, and rational case.
- Bijective counting of plane bipolar orientations and Schnyder woods
- Title not available (Why is that?)
- Loop models on random maps via nested loops: the case of domain symmetry breaking and application to the Potts model
- Chromatic Sums for Rooted Planar Triangulations: The Cases λ = 1 and λ = 2
- Dichromatic polynomials and Potts models summed over rooted maps
- Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation
- Chromatic sums revisited
- A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths
- Improved upper bounds for self-avoiding walks in \(\mathbb Z^d\)
- Bijective counting of involutive Baxter permutations
- Counting coloured planar maps: differential equations
- Effect of confinement: polygons in strips, slabs and rectangles
Cited In (8)
- On the number of planar orientations with prescribed degrees
- On the Number of α-Orientations
- Counting planar Eulerian orientations
- Asymptotic enumeration of orientations
- The six-vertex model on random planar maps revisited
- Eulerian orientations and the six-vertex model on planar maps
- Inhomogeneous restricted lattice walks
- The generating function of planar Eulerian orientations
Uses Software
This page was built for publication: On the number of planar Eulerian orientations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2400972)
