Albenque, Duchi and Schabanel (arXiv:2607.22208, July 2026) constructed a recursive bijection between labeled quadrangulations - the planar duals of Eulerian orientations of quartic maps, i.e. the ice (six-vertex) model on random planar maps - and well-charged unary-binary trees of charge 1, thereby answering a question of Bousquet-Mélou and Elvey Price. Their paper explicitly poses three linked open problems which together ask for a canonical bijective theory: (1) a genuinely non-recursive bijection, since even the direct face-exploration description of the known construction has a correctness proof that relies on the recursive patch decomposition; (2) an explicit bijection preserving the refined statistics - local minima and maxima of the labeling versus right and left leaves of the tree - whose existence at the level of joint distributions is supported by computational evidence but is unproven; and (3) an explicit bijection, for the colorful subclass (quartic Eulerian orientations without alternating vertices), between the tree family produced by restricting the new bijection and the balanced binary-tree model of Bousquet-Mélou and Elvey Price. The problem asks for constructions and proofs resolving these three components. As of August 2026, all three components remain open.

Background

A planar map is a connected graph embedded in the sphere, considered up to deformation; loops and multiple edges are allowed, and throughout the subject maps are taken rooted, i.e. equipped with a distinguished oriented edge. An Eulerian orientation of a map is an orientation of its edges such that every vertex has equally many incoming and outgoing edges. On quartic maps (all vertices of degree 4), Eulerian orientations are the map analogue of the ice model of statistical mechanics, also known as the six-vertex model, since each degree-4 vertex then sits in one of the six standard ice configurations. By planar duality, a quartic map carrying an Eulerian orientation is equivalent to a labeled quadrangulation: a rooted quadrangulation (all faces of degree 4) whose vertices carry integer labels that change by exactly 1 in absolute value along every edge, with the root vertex labeled 0 and the co-root vertex labeled 1; the orientation of each dual edge is recovered from which endpoint carries the larger label. A vertex of a labeled quadrangulation is a local minimum (resp. local maximum) if its label is strictly smaller (resp. strictly larger) than the labels of all its neighbors.

The enumeration of these objects has a two-decade history. Bonichon, Bousquet-Mélou, Dorbec and Pennarun (2017) initiated the combinatorial study and obtained algebraic families of super- and sub-sets approximating the counted class. Elvey Price and Guttmann (2018) computed many initial coefficients and conjectured the unusual asymptotic form μn/(nlog⁡n)2\mu^{n}/(n\log n)^{2} for the number of Eulerian orientations, in agreement with earlier physics predictions for the six-vertex model on a random lattice. Bousquet-Mélou and Elvey Price (2020) then solved the problem exactly, expressing the generating functions of Eulerian orientations of planar maps and of quartic planar maps as inverses (for composition) of simple hypergeometric series and proving the predicted asymptotics. Their paper also gave tree interpretations of the underlying series and described the bijective understanding of these equidistributions as wide open.

A unary-binary tree is a rooted plane tree in which every inner vertex has one or two children; its charge is the number of binary vertices minus the number of unary vertices, and the charge of a subtree is defined analogously. Such a tree is well-charged if every subtree rooted at an inner vertex has nonzero charge. A leaf is a left or right leaf when it is, respectively, the left or right child of a binary vertex. In a 2025 refinement, Bousquet-Mélou and Elvey Price counted quartic Eulerian orientations by vertices, alternating vertices (vertices whose four incident edges point alternately in and out around the vertex) and clockwise faces, and proved refined tree interpretations: in particular, for every n≥1n \ge 1 and j≥0j \ge 0, well-charged unary-binary trees of charge 1 with n+2n+2 leaves and jj right leaves are equinumerous with labeled quadrangulations with nn faces and jj local minima. They also documented computational evidence (verified by brute force up to small sizes) that the joint distribution of left and right leaves matches the joint distribution of local maxima and local minima.

Albenque, Duchi and Schabanel (2026) answered this question with an explicit recursive bijection between labeled quadrangulations with nn faces and well-charged unary-binary trees of charge 1 of size n+1n+1 (that is, with n+2n+2 leaves), extended to trees of every integer charge through families of maps with boundary called patches and D-patches. The proof proceeds by a recursive decomposition of the quadrangulation into eight construction types, including subpatch expansions with label shifts −1-1 and +2+2 that mix the signs of the labels; the decomposition also yields bijectively the patch generating-function equation of Bousquet-Mélou and Elvey Price and supports Boltzmann samplers (random generators drawing each object with probability proportional to a fixed weight). However, the construction does not preserve the refined statistics: in the mixed-sign expansion steps, local extrema are created and destroyed in a way the recursion cannot track. An appendix gives a direct face-exploration algorithm producing the same tree and a procedure to draw the map back on the tree, but the proofs that these are inverse bijections still rely on the recursive decomposition.

The third component concerns the colorful subclass. A colorful quadrangulation is a labeled quadrangulation in which the labels around every face read (r−1,r,r+1,r)(r-1, r, r+1, r) in cyclic order for some integer rr; dually this is the subclass of quartic Eulerian orientations without alternating vertices. This subclass, also studied through Budd's rigid quadrangulations in connection with Jackiw-Teitelboi gravity (a two-dimensional dilaton gravity model whose discrete path-integral formulations are built from random quadrangulations), is enumerated by a simpler tree model of Bousquet-Mélou and Elvey Price: rooted plane binary trees whose edges are solid or dashed, of charge 0 (number of solid edges minus number of dashed edges), containing no proper subtree of charge 0; such trees are called balanced, and the model refines to special leaves (right children incident to a dashed edge), which correspond to local minima. Zonneveld gave a direct bijective proof of the colorful generating function through different trees (so-called H-trees and Q-trees, arising from rigid quadrangulations), but stated that a direct bijection between his trees and the balanced binary-tree model remains open.

Problem Statement

The common objective is to replace the recursive bijection of Albenque, Duchi and Schabanel by a canonical bijective theory of the ice model on quartic maps, at the level of directness of the construction, preservation of refined statistics, and unification with the tree models of the colorful subclass. Concretely, resolve the three open problems posed in arXiv:2607.22208.

(Q1) Genuinely non-recursive bijection. Construct a bijection between labeled quadrangulations (equivalently, Eulerian orientations of quartic maps) and well-charged unary-binary trees of charge 1 whose two directions are given by direct descriptions - not via the recursive patch decomposition - and prove that the two directions are inverse to each other by an argument that does not proceed through that recursive decomposition, in the sense in which classical closure-type bijections, which turn labeled trees into maps by a local closing rule, are direct. The face-exploration and tree-drawing constructions of the source paper's appendix do not qualify, since their correctness proofs are recursive in essence.

(Q2) Statistics-preserving bijection. Construct an explicit bijection between labeled quadrangulations and well-charged unary-binary trees of charge 1 that maps local minima of the labeling to right leaves of the tree and local maxima to left leaves, thereby giving a bijective proof of the refined enumeration of Bousquet-Mélou and Elvey Price and of the conjectured equality of joint distributions; a full solution naturally addresses the authors' stated conjecture that the same correspondence holds for well-charged trees and patches of arbitrary positive charge, and, with an adapted notion of local extrema (in which the root vertex and its neighbours do not count), for negative charges and D-patches.

(Q3) Colorful subclass. For colorful quadrangulations (equivalently, quartic Eulerian orientations without alternating vertices), construct an explicit bijection between the family of trees obtained by restricting the source paper's bijection to this subclass and the balanced binary-tree model of Bousquet-Mélou and Elvey Price (binary trees with solid and dashed edges, charge 0, no proper balanced subtree); equivalently, make the connection among the three known tree encodings of the colorful subclass - the balanced binary trees, Zonneveld's H-trees and Q-trees, and the restriction family - explicit, ideally preserving the refinement by local minima versus special leaves.

A complete answer provides constructions and full proofs for all three components; each component is a separately verifiable deliverable, and they are linked by the common objective above. Partial answers that resolve one or two components constitute partial progress on the problem.

References

  1. Marie Albenque, Enrica Duchi, Juliette Schabanel (2026), A tree bijection for Eulerian orientations on quartic maps, arXiv:2607.22208, https://arxiv.org/abs/2607.22208 (source of the three open problems)
  2. Mireille Bousquet-Mélou, Andrew Elvey Price (2025), Refined enumeration of planar Eulerian orientations, arXiv:2503.15046, https://arxiv.org/abs/2503.15046
  3. Mireille Bousquet-Mélou, Andrew Elvey Price (2020), The generating function of planar Eulerian orientations, Journal of Combinatorial Theory Series A 172, 105183, doi:10.1016/j.jcta.2019.105183, https://arxiv.org/abs/1803.08265
  4. Bart Zonneveld (2025), A tree bijection for rigid quadrangulations, arXiv:2509.24787, https://arxiv.org/abs/2509.24787
  5. Timothy Budd (2025), Discrete flat disks: rigid quadrangulations, arXiv:2509.24785, https://arxiv.org/abs/2509.24785
  6. Nicolas Bonichon, Mireille Bousquet-Mélou, Paul Dorbec, Claire Pennarun (2017), On the number of planar Eulerian orientations, European Journal of Combinatorics 65, pp. 59-91, doi:10.1016/j.ejc.2017.04.009, https://arxiv.org/abs/1610.09837
  7. Andrew Elvey Price, Anthony J. Guttmann (2018), Counting planar Eulerian orientations, European Journal of Combinatorics 71, pp. 73-98, doi:10.1016/j.ejc.2018.02.040, https://arxiv.org/abs/1707.09120