The Setting
In the block-core decomposition of rooted Fortuin-Kasteleyn planar maps with edges, encoded by a Galton-Watson tree conditioned on size with exploration walk , graph distances between corners are governed by increments of along tree paths. Given two nodes visited in preorder, how does the path length to their lowest common ancestor constrain the path lengths of nodes visited between them, and how closely does the walk increment from an intervening minimum approximate the real graph distance between their poles?
Chord Graphs and Two-stack Matchings
For a natural number , the set of chord opening endpoints of a permutation of is the subset of consisting of all indices satisfying , and each such index is a chord opening endpoint of .✦ The chord crossing relation on the chord opening endpoints of a permutation of is the relation holding between two chord opening endpoints whenever either or .✦ The chord intersection graph of a permutation on is the simple graph on whose edges are the pairs of chord opening endpoints satisfying the chord crossing relation.✦
The alphabet of typed burger-order letters consists of burger tokens and order tokens each carrying a Boolean type in ( or ).✦ The typed word stack execution of a list of typed burger-order letters from a freshest-first stack of Boolean types is the evaluation of step by step starting from , returning either a final stack of Boolean types or failure on an illegal closure.
A non-crossing arch matching on a list in a set is a list of ordered pairs in such that is generated inductively from empty lists by either prepending an unmatched element of to while leaving unchanged, or, from non-crossing arch matchings on a list and on a list , placing a pair before the concatenation of and to match the concatenation of , , , and .✦ The list of endpoints of a list of pairs in a set is the list in obtained by flattening each pair in into and in order.✦
A two-stack matching certificate for a map along a list in a set is a pair of non-crossing arch matchings and on such that (where denotes list concatenation) is a permutation of , every pair in has a burger token of type and an order token of type , and every pair in has a burger token of type and an order token of type .✦ The arch transposition product of a list of pairs in a set is the permutation of defined recursively as the identity on the empty list and as when begins with followed by , where is the transposition swapping and .✦ The stack matching mate permutation of a two-stack matching certificate on is the permutation of .
A word of typed burger-order letters satisfies the connected core word condition if there exist a natural number , a map whose list of values equals , and a two-stack matching certificate for along such that and every element of is reachable from in .✦ A connected typed core of length is a word of typed burger-order letters satisfying the connected core word condition, and its positions are the corners of .✦
Core Trees and Real Graph Distances
An ordered tree of cores is an inductive tree that is either a leaf or a branch consisting of a connected typed core and a family of child ordered trees of cores indexed by the corners of .✦ The set of core tree nodes of an ordered tree of cores consists of a single root node when is a leaf, and, when is a branch , of the root of together with all pairs where is a corner of and .✦ The set of core tree darts of an ordered tree of cores is the empty set when is a leaf, and, when is a branch , consists of all corners of the root core together with all pairs where is a corner of and .✦
The core tree dart label of an ordered tree of cores is the map sending a root corner dart of a branch to the -th letter of and a child dart to .✦ The core tree dart list of an ordered tree of cores is the empty list if is a leaf, and for a branch is the concatenation over of the root corner dart followed by the darts of lifted as pairs .✦ The core tree stack matching of an ordered tree of cores is a two-stack matching certificate for along .
The preorder node index of a node in an ordered tree of cores vanishes when is a leaf or is the root of a branch, and for a child node of a branch equals plus the number of nodes in the child subtrees for plus .✦ Writing for the corner increment of a connected typed core at corner , the node route length of a node in an ordered tree of cores is when is a leaf or is the root of a branch, and at a child node of a branch is given by (1)✦ The common route length of two nodes in an ordered tree of cores is when is a leaf, when either or is the root of a branch, or when and lie in distinct child subtrees of a branch, and for two nodes and in the same child subtree of a branch is given by (2)✦
The maximum core degree of an ordered tree of cores is when is a leaf, and for a branch is given by (3)✦
The node pole dart of a node in an ordered tree of cores is either a dart in or undefined: a leaf node has no pole dart, the root of a branch has the entry corner dart of , and a child node in has if is defined and otherwise the next corner dart of after under the cyclic shift.✦
For a permutation of a set , the cycle vertex set is the set of cycle equivalence classes of under ✦, and the cycle vertex projection is the map sending each to its cycle class in .✦ Given an edge permutation and a vertex rotation on a set , the permutation wedge dart graph is the simple graph on in which two distinct vertices are adjacent whenever there exists with .✦ On an ordered tree of cores with stack matching , set , where is the permutation of formed from ; writing for graph distance in a simple graph , the real graph distance between two darts is defined by (4)✦
The Claim
Theorem 1. Let be an ordered tree of cores.
If satisfy , then (5)✦
If satisfy , then there exists a node with such that (6)✦
Let satisfy , and let satisfy and . Suppose is a function and and are real numbers such that for every , and for every satisfying . Then (7)✦
In the paper, the result reads: if and is the lowest common ancestor of the nodes and , then , where stands for the exploration walk (with ) and stands for .
What Is Checked
The bounds (5) and (6) are stated over any ordered tree of cores and nodes ordered by preorder node index ( with for the intervening route lower bound (5), and with for the low intervening node bound (6)). The pole distance walk comparison (7) is stated over any , nodes with , pole darts of and , an arbitrary function , and real numbers and satisfying uniform route-length approximation and local minimality of at .
Whenever the list of values obtained by applying a map along a list in a set has its typed word stack execution from an empty stack terminate in an empty stack, there exists a two-stack matching certificate for along .✦ For every ordered tree of cores , the dart-label sequence along reduces an empty stack to an empty stack under typed word stack execution, providing the core tree stack matching . On chord opening endpoints of a permutation, the chord crossing relation is symmetric and irreflexive.