The Setting
Take a rooted finite planar map represented as a rotation system and decomposed via a two-stack burger-order encoding into an ordered tree of connected cores. Each nonroot node of this tree designates a pole vertex in the map, so placing equal mass on all nonroot tree nodes pushes forward to a measure on map vertices. The question is whether this corner-pole measure coincides with the normalized vertex degree measure, where each dart contributes equal weight to the vertex around which it rotates.
Rooted Planar Maps and Degree Measure
The dart set of a planar map with edges () is the set indexing its directed edges, with designated as the root dart.✦ The orbit of a dart under a permutation of is the cycle equivalence class of under containing ✦, and the orbits of are these equivalence classes.✦ The spanning subgraph determined by permutations and of and a subset of the orbits of is the simple graph on the orbits of in which two orbits and are adjacent whenever some dart satisfies , , and .✦
A pair of permutations of satisfies the planar map conditions if is a fixed-point-free involution, the spanning subgraph determined by , , and all orbits of is connected, and the number of orbits of plus the number of orbits of equals .✦ A labelled planar map with edges is a pair of permutations of satisfying the planar map conditions.✦ An isomorphism of rooted maps between two labelled planar maps and with edges is a permutation of fixing the root dart such that and for every .✦ A rooted planar map with edges is an equivalence class of labelled planar maps with edges under the equivalence relation generated by isomorphisms of rooted maps.✦
For a rooted planar map with edges, the vertex rotation permutation on is the second permutation of a representative labelled planar map of , cyclically ordering the darts around each vertex.✦ The vertices of a rooted planar map with edges are the orbits of on .✦ Given a rooted planar map with edges and writing for the Dirac unit mass at a vertex , the normalized vertex degree measure of is the measure on defined by (1): (1)✦
Two-stack Matchings and Permutation Wedges
The typed burger-order alphabet is the set of tokens consisting of burger tokens and order tokens carrying one of two boolean types (true or false).✦ The typed word stack execution of a finite word in against a stack of boolean types stored freshest-first evaluates the word letter by letter against the stack, with each order consuming the freshest eligible burger, and returns either the resulting stack upon success or failure upon an illegal closure.✦
A non-crossing arch matching along a finite list of elements of a set is a list of ordered pairs in built recursively from the empty list on the empty list by skipping an unmatched element or by pairing elements and with prepended to the concatenation of non-crossing arch matchings on the sublist strictly between and and on the sublist following .✦ The endpoints list of an arch list in is the list in collecting the first and second coordinates of each pair in in order.✦ The arch transposition product of an arch list in is the permutation of defined recursively as the identity on the empty list and as when precedes the tail .✦
A two-stack matching certificate for a function along a finite list in is a pair of non-crossing arch matchings and along whose combined endpoints list is a permutation of , with every pair matching a true burger at to a true order at and every pair matching a false burger at to a false order at .✦ The stack matching mate permutation of a two-stack matching certificate is the arch transposition product of the concatenation of followed by .✦ For a function and a finite list in , whenever typed word stack execution on the mapped word of under starting from an empty stack terminates in an empty stack, the matching-of-empty-word construction produces a two-stack matching certificate for along .✦
The permutation-wedge vertices of a permutation of a set are the cycle equivalence classes of under ✦, and the cycle vertex projection sends each to its cycle class .✦ The permutation-wedge dart graph of permutations and of a set is the simple graph on the permutation-wedge vertices of in which two vertices and are adjacent whenever some satisfies and .✦ For a two-stack matching certificate along a finite list in , let be the cyclic permutation formed by and let ; the typed matching distance between elements is the extended graph distance between and in the permutation-wedge dart graph of and .✦
A chord opening endpoint (or opener) of a permutation of () is an index in satisfying .✦ Two openers and of a permutation of satisfy the chord crossing relation when their endpoints interlace, meaning either or .✦ The chord intersection graph of a permutation of is the simple graph on the openers of whose edges are the pairs of crossing openers.✦
Ordered Trees of Cores
The length of a finite word or list is the number of elements of . A finite word of letters in satisfies the connected core word condition if there exist an integer , a map whose list of values equals , and a two-stack matching certificate for along whose mate permutation has an opener at index from which every opener of is reachable in the chord intersection graph of .✦ A connected typed core is a finite word of letters in satisfying the connected core word condition.✦ An ordered tree of cores is a tree defined recursively as either a leaf or a branch carrying a connected typed core together with child ordered trees of cores indexed by .✦ The word of an ordered tree of cores is the empty word when is a leaf, and when is a branch with core and child subtrees it is the word formed by inserting each child word into at corner .✦
The core tree darts of an ordered tree of cores form a finite set defined recursively: a leaf has no darts, while at a branch with core and child subtrees , a dart in is either a position of or a position paired with a dart in .✦ The core tree dart label of a dart in an ordered tree of cores is the -th letter of when is a position of the branch core , and is the core tree dart label in when belongs to the child subtree .✦ The core tree dart list of an ordered tree of cores lists all darts in in recursive substitution order: it is empty at a leaf, and at a branch with core and child subtrees it concatenates, for , the core dart at followed by the dart list inside .✦ The core tree stack matching of an ordered tree of cores is the two-stack matching certificate obtained by applying the matching-of-empty-word construction along with label assignment .✦ A function from the darts of an ordered tree of cores to a set is vertex-constant on if whenever satisfy .✦
The core tree nodes of an ordered tree of cores are the vertices of itself, keeping a distinct trivial leaf at every empty corner word without identifying coincident map poles: a leaf has a single node, while a branch with core and child subtrees has a branch root node together with, for each , the nodes of .✦ An optional core label is a mark carrying either a connected typed core or nothing✦, and the core tree label sequence of an ordered tree of cores is the list of optional core labels returning a singleton empty mark at a leaf and, at a branch with core and child subtrees , prepending to the concatenation of the label sequences .✦ The preorder node index of a node in an ordered tree of cores is the nonnegative integer defined recursively to be at a leaf or branch root, and plus the total length of the label sequences preceding plus the preorder node index of in when belongs to the -th child subtree of a branch.✦ The preorder node word equivalence of an ordered tree of cores is the bijection from onto obtained by reindexing the bijection from onto that maps each node to its preorder node index.✦
For an ordered tree of cores and a node , the node pole dart is either a dart in or absent: it is absent at a leaf; at a branch with core and child subtrees , it is the entry core dart of at the branch root, while for in it is the image of in if is present and otherwise the core dart of at the next slot for .✦ Given an ordered tree of cores , a rooted planar map with edges, and a bijection , the realized pole of a node is when is present and the root-dart orbit otherwise.✦ The nonroot pole vertex associated with an ordered tree of cores , a rooted planar map with edges, a bijection , and an index is given by (2): (2)✦
The Claim
Theorem 1. Let be an ordered tree of cores, a rooted planar map with edges, and a bijection satisfying for every ; then (3) holds: (3)✦ Let be a cancellative commutative additive monoid, an ordered tree of cores, a vertex-constant function, and , and let be the extension returning on a present dart and when absent; then (4) holds: (4)✦ For every rooted planar map with edges, its normalized vertex degree measure satisfies (5): (5)✦
In the paper, the result reads: the uniform probability measure on the nonroot tree nodes, pushed forward by the pole projection , is exactly , where is the pole map on tree nodes and is the normalized degree measure on a map with edges. For maps indexed by with edges, the library states this correspondence through the unnormalized Dirac-sum identity (3) and dart-sum identity (4) together with the total-mass normalization (5) of .
What Is Checked
The claims are stated over an arbitrary ordered tree of cores , an arbitrary rooted planar map with edges () in (3) and (5), a bijection satisfying for every in (3), and a vertex-constant function into a cancellative commutative additive monoid with default value in (4).
For every ordered tree of cores , the label sequence satisfies ✦, and every node in has preorder node index strictly less than .✦