The Setting
Consider a rooted planar map with edges assembled recursively from an ordered tree of connected cores, where each tree node carries a route length summing core increments from the root and determines a pole vertex in . How closely does the graph distance between the poles of two nodes match the route distance formed from their route lengths and the route length of their last common ancestor, and do the nonroot poles cover every vertex of ?
Rooted Planar Maps and Wedge Graphs
For , the dart set of a map with edges is the finite set , whose elements are called darts.✦ An orbit of a permutation on is an equivalence class of darts belonging to the same cycle of ✦, and the orbit map on is the map sending each dart to its -cycle.✦ Given an edge-reversal permutation , a vertex-rotation permutation on , and a set of orbits of , the spanning subgraph on the orbits of is the simple graph in which two distinct orbits and of are adjacent whenever some dart satisfies and .✦
A labelled planar map with edges is a pair of permutations of such that is a fixed-point-free involution on , the spanning subgraph formed using all orbits of is connected, and the number of orbits of plus the number of orbits of equals .✦ Two labelled planar maps and on are isomorphic as rooted maps if there exists a permutation of fixing the root dart such that and .✦ A rooted planar map with edges is an equivalence class of labelled planar maps with edges under the equivalence relation generated by root-preserving map isomorphisms.✦ For a rooted planar map with a chosen representative , the vertex-rotation permutation of is the permutation cyclically ordering the darts around each vertex✦, and the vertex set of is the set of orbits of .✦
For a vertex-rotation permutation on a finite dart set , the permutation wedge vertex set of is the set of cycle equivalence classes of under ✦, with the cycle projection mapping each dart to its -cycle.✦ Given a permutation on , the permutation wedge dart graph is the simple graph on in which two distinct cycles and are adjacent whenever some dart satisfies , and denotes the graph distance between and in .✦
Typed Words, Arch Matchings, and Cores
Let denote the alphabet of typed burger-order letters, each of which is either a burger token or an order token carrying one of two boolean types ( or ).✦ Given a boolean stack stored freshest-first, typed word stack execution evaluates a word of letters in against the stack, returning the final boolean stack upon success or failing on an illegal closure.✦
A non-crossing arch matching on a finite list of elements from a set is a list of ordered pairs from defined inductively: the empty list matches the empty list; any non-crossing arch matching on a list remains one when is preceded by an unmatched element ; and given non-crossing arch matchings on and on , placing before the concatenation of and forms a non-crossing arch matching on the list obtained by placing , , , and in order.✦ The endpoints of a list of pairs in form the list of first and second coordinates of all pairs in ✦, while the arch transposition product is the permutation of equal to the identity on the empty list and defined recursively by when consists of followed by , where swaps and .✦
Given a letter assignment along a list of elements of , a two-stack matching certificate consists of non-crossing arch matchings and on whose combined endpoints form a permutation of , such that every pair assigns a burger token to and a order token to , and every pair assigns a burger token to and a order token to .✦ The stack matching mate permutation of a two-stack matching certificate is the arch transposition product of the concatenation of and .✦
For an integer and a permutation on , a chord opening endpoint of is an index in satisfying .✦ Two openers and of satisfy the chord crossing relation when either or ✦, and the chord intersection graph of is the simple graph on its openers whose edges join crossing pairs.✦ A word of letters in satisfies the connected core word condition if its index sequence along admits a two-stack matching certificate such that is an opener of and every opener of is reachable from in the chord intersection graph of .✦ A connected typed core is a word of letters in satisfying the connected core word condition✦, and an optional core label is either a connected typed core or an empty mark.✦
Ordered Trees of Cores, Poles, and Routes
An ordered tree of cores is defined inductively: it is either a leaf or a branch formed by a connected typed core and a family of child ordered trees of cores indexed by the corners of .✦ A core tree node of an ordered tree of cores is a vertex of itself (without identifying coincident map poles): a leaf has a single node, while at a branch a node is either the branch root or a pair consisting of a corner index and a core tree node of .✦ A core tree dart of an ordered tree of cores is a dart of the recursively substituted word: a leaf has no darts, while at a branch a dart is either a position of or a pair with and a core tree dart of ; the set of all core tree darts of is denoted by .✦
For an ordered tree of cores and a dart , the core tree dart label of is the letter defined inductively: at a branch , a position of carries the -th letter of , and a dart in child subtree keeps its label .✦ The core tree dart list of an ordered tree of cores is the list of all darts of in recursive substitution order: it is empty at a leaf, and at a branch it concatenates, for , the core dart at followed by the dart list in child subtree .✦ The word of an ordered tree of cores is the word of letters in defined inductively: at a leaf, is empty, while at a branch it is formed by inserting each child word into at corner .✦ For any ordered tree of cores , the core tree stack matching is the two-stack matching certificate for along constructed from the empty-stack execution of .✦
The core tree label sequence of an ordered tree of cores is the list of optional core labels in preorder: the single empty mark at a leaf, and at a branch the label followed by the concatenation of .✦ For a core tree node of an ordered tree of cores , the preorder node index equals at a leaf or branch root, and for a node in child subtree of a branch is given by (1): (1)✦ For an ordered tree of cores , the preorder node word bijection is the bijection from the nodes of onto sending the root to and the nonroot nodes to , obtained by indexing nodes by the preorder node index .✦
For an ordered tree of cores and a core tree node of , the node pole dart is either a dart in or absent: at a leaf it is absent; at a branch , it equals dart of when is the branch root, and for a node in child subtree it equals the image of in if is present in , and otherwise the next corner of after under the cyclic shift.✦ Given an ordered tree of cores , a core tree node of , a rooted planar map with edges, and a bijection , the realized pole of is the vertex when is present, and the root vertex when is absent.✦ The nonroot pole map of an ordered tree of cores , a rooted planar map with edges, and a bijection assigns to each the realized pole .✦
Writing for the increment of a connected typed core at corner , the node route length of a core tree node of an ordered tree of cores is the sum of core increments along the path from the root of to given by (2): (2)✦ For two core tree nodes and of an ordered tree of cores , the common route length is the sum of core increments along their shared root path to their last common ancestor given by (3): (3)✦ The maximum core degree of an ordered tree of cores is the largest core word length in , equal to at a leaf and to at a branch .✦
The vertex-rotation permutation of an ordered tree of cores is the permutation on , where is the cyclic permutation of , and the real graph distance between two darts is the distance in the permutation wedge dart graph given by (4): (4)✦
The Claim
Theorem 1. Let be an ordered tree of cores, let and be two core tree nodes of , and suppose and have node pole darts satisfying and . Then the real graph distance between and satisfies (5)✦ Furthermore, if , is a rooted planar map with edges, and is a bijection satisfying for every , then the nonroot pole map satisfies (6)✦
In the paper, the result reads: if is the last common ancestor of two tree nodes and and is the maximum offspring number, then the all-edge graph distance on and the pole map from tree nodes to satisfy , and is onto, where is the route length. The bound (5) expresses this comparison on an ordered tree of cores via the permutation wedge distance , the common route length , and the maximum core degree rather than , , and , while (6) restricts the pole map to nonroot tree nodes under a rotation-intertwining dart bijection.
What Is Checked
The two claims are stated over an ordered tree of cores , two nodes and of possessing node pole darts and , the real graph distance in the permutation wedge dart graph of , the node route length , the common route length , and the maximum core degree , together with a rooted planar map with edges and a bijection satisfying for every dart . Beyond these claims, the library also holds that for a set , any letter assignment along a list of elements of whose typed stack execution from the empty stack finishes with an empty stack admits non-crossing arch matchings and on whose combined endpoints permute , with pairing burgers to orders and pairing burgers to orders.✦ It also holds for every ordered tree of cores that ✦ and that for every node of .✦