Counting planar Eulerian orientations. (June 2018)

• Record Type: Journal Article
• Authors: Elvey-Price, Andrew; Guttmann, Anthony J.
• Is Part Of: European journal of combinatorics. Volume 71(2018)
• Page Start: 73
• Page End: 98
• Publication Date: 2018-06
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.02.040
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Inspired by the paper of Bonichon et al. (2016), we give a system of functional equations which characterise the ordinary generating function, U ( x ), for the number of planar Eulerian orientations counted by edges. We also characterise the ogf A ( x ), for 4-valent planar Eulerian orientations counted by vertices in a similar way. The latter problem is equivalent to the 6-vertex problem on a random lattice, widely studied in mathematical physics. While unable to solve these functional equations, they immediately provide polynomial-time algorithms for computing the coefficients of the generating function. From these algorithms we have obtained 100 terms for U ( x ) and 90 terms for A ( x ) . Analysis of these series suggests that they both behave as c o n s t ⋅ ( 1 − μ x ) ∕ log ( 1 − μ x ), where we conjecture that μ = 4 π for Eulerian orientations counted by edges and μ = 4 3 π for 4-valent Eulerian orientations counted by vertices.