The Setting
Fix a Potts parameter and sample a rooted planar map with edges together with a subset of its edges under the Fortuin-Kasteleyn (FK) random-cluster measure. Rescaling graph distances on by for an appropriate constant and weighting each vertex by its normalized degree produces a sequence of random compact metric probability spaces. The question is whether these rescaled FK-decorated maps converge weakly in the Gromov-Hausdorff-Prokhorov (GHP) topology as to the Brownian continuum random tree (CRT).
Planar Maps and the Fortuin-kasteleyn Measure
For , the dart set of a map with edges is the set indexing its directed edges.✦ For a permutation on , the orbit of a dart is the equivalence class of darts belonging to the same cycle of ✦, and the orbit set is the set of all orbits of .✦ Given permutations and on and a subset , the spanning subgraph is the simple graph on in which distinct orbits are adjacent whenever some dart with satisfies or .✦
A pair of permutations on satisfies the planar map conditions if is a fixed-point-free involution, the all-edge spanning subgraph is connected, and the numbers of orbits under and orbits under sum to .✦ A labelled planar map of size is a pair of permutations on satisfying the planar map conditions.✦ An isomorphism of rooted maps between two labelled planar maps and of size is a permutation of fixing dart (the root dart) such that and .✦ A rooted planar map of size is an equivalence class of labelled planar maps under the equivalence relation generated by root-preserving map isomorphisms.✦
Given a representative of a rooted planar map of size , the dart reversal involution of is ✦, the vertex rotation permutation of is ✦, the edge set of is the orbit set ✦, and the vertex set of is the orbit set .✦ For an edge subset , the spanning subgraph of induced by is .✦ A spanning tree of a rooted planar map is a subset of whose spanning subgraph is connected and acyclic. A tree-decorated rooted map of size is a pair consisting of a rooted planar map of size and a spanning tree .✦
For an edge subset on a rooted planar map of size , the cluster count is the number of connected components of .✦ At real Potts parameter , the FK-decorated map weight of is given by (1): (1)✦ and the finite FK partition function at size sums (1) over all rooted planar maps of size and all subsets .✦ The normalized vertex degree measure on is the probability measure assigning mass per dart to its vertex , giving each vertex with degree mass .✦
Gromov-hausdorff-prokhorov Convergence and the Brownian Tree
A metric measure space presentation consists of a carrier set , a distance function , a -algebra on , and a measure on .✦ A metric measure space presentation is a compact metric probability space if is the distance of a compact metric space structure on , is the Borel -algebra of that metric space, and .✦ Given two metric measure space presentations and , an isometric amalgamation pseudometric between and is a pseudometric on the disjoint union that agrees with on and with on .✦ For an isometric amalgamation pseudometric on the disjoint union of two presentations and , the GHP ambient embedding cost is the maximum of the Hausdorff distance between the embedded images of and and the Lévy-Prokhorov distance between the pushforwards of and under the canonical inclusions into with its Borel -algebra.✦ The GHP distance between two metric measure space presentations and is the infimum in of the GHP ambient embedding cost over all isometric amalgamation pseudometrics on .✦
For a rooted planar map of size and a scale factor , the rescaled map metric measure space is the presentation on with distance , where is the graph distance in , discrete -algebra on , and normalized vertex degree measure .✦ A real-valued function on metric measure space presentations is a bounded continuous GHP test if is uniformly bounded on all presentations and, for every compact metric probability space and every , there exists such that whenever is a compact metric probability space with .✦ The finite FK map expectation of a bounded continuous GHP test at parameter , scale , and size is defined by (2): (2)✦
For a function , the excursion tree pseudometric on is defined by (3): (3)✦ For a function , the excursion real tree coded by is the quotient of by the equivalence relation generated by , with canonical excursion tree projection .✦ For a function , the excursion tree metric measure space of the excursion real tree is the presentation on with the quotient distance induced by , the Borel -algebra of the quotient topology, and the pushforward of Lebesgue measure on under .✦ Given three independent Brownian motions on a probability space , the normalized Brownian excursion at is the three-dimensional Bessel bridge (4): (4)✦ For a bounded continuous GHP test and three independent Brownian motions on a probability space , the Brownian CRT test expectation is the integral .✦
The Inventory Bijection and Connected Cores
Given an involution on and an edge-orbit subset , the partial dart reversal is the permutation on that applies to darts with and fixes all other darts.✦ A canonical rooted tree map of size is a labelled planar map of size equipped with an edge-orbit subset such that the tour permutation equals the standard cyclic permutation on .✦ Relabelling darts of a representative of a tree-decorated rooted map along its tour yields a unique canonical representative called its tree normal form✦, identifying tree-decorated rooted maps of size bijectively with canonical rooted tree maps of size .✦
An inventory FK model parameter tuple is a parameter specification fixing a probability , which determines a flexible order parameter and an inventory radius parameter .✦ The inventory alphabet consists of two burger types, two fixed orders (one for each burger type), and one flexible order.✦ An inventory stack evaluation state is a pair consisting of a list of pending orders and a freshest-first stack of burgers✦; evaluating a word of inventory letters starts from empty pending orders and an empty burger stack and updates the state letter by letter, and a word of inventory letters is empty-reducing if this reduction ends with both lists empty.✦ Under parameter , the letter distribution assigns mass to each burger type, to the flexible order, and to each fixed order.✦ Under the independent and identically distributed (i.i.d.) stream measure of this distribution on infinite letter sequences, is the probability that the first letters form an empty-reducing word✦, and the total empty-word probability under is the sum .✦
A typed burger-order letter is a burger or an order carrying one of the two burger types.✦ Typed stack execution runs a word of typed letters against a freshest-first stack of burger types, where an order consumes the freshest eligible burger and fails on an illegal closure✦; a stack-emptying typed word is a typed word whose execution from an empty stack terminates successfully with an empty stack.✦ For a typed word , the flexible closing count is the number of flexible order closures encountered during typed stack execution from an empty stack✦, and the word monomial weight of at parameters is .✦ Given a canonical rooted tree map of size , its canonical tour matching word is the typed word assigning to each dart a burger if and an order if , of the type indicating whether .✦ A successful dart word of size is a stack-emptying typed word of length ✦, and the canonical tour matching word yields a bijection between tree-decorated rooted maps of size and successful dart words.✦
A non-crossing arch matching on a list of positions is a collection of disjoint pairs of positions that form nested non-crossing arches while possibly leaving unmatched elements skipped.✦ A two-stack matching certificate for a typed word decomposes its positions into two non-crossing arch matchings covering all positions, one pairing burgers with orders of the first type and the other pairing those of the second type✦, whose mate permutation is the product of all arch transpositions.✦ For a permutation on , the chord openers of are the indices such that ✦, two openers and cross if or ✦, and the chord intersection graph of is the simple graph on the chord openers in which two openers are adjacent whenever they cross.✦ A connected typed core is a typed word of length admitting a two-stack matching certificate whose mate permutation has an opener at index from which every opener is reachable in the chord intersection graph. For a connected typed core of length , the core vertex rotation permutation is the cyclic shift composed with the transpositions of the first-type arches of the core stack matching✦, the isolated core map graph of is the simple graph on the cycle vertices of this permutation with an edge between distinct vertex cycles whenever the mate permutation maps a position in one cycle to the other✦, and the core corner metric increment at corner is the graph distance in this isolated core graph from the vertex of the entry corner to the vertex of the corner obtained by applying the cyclic shift to .✦
An optional core label is either empty, with arity , or a connected typed core , with arity .✦ An ordered tree of cores is a rooted plane tree whose leaves carry the empty label and whose internal nodes carry a connected typed core together with ordered child subtrees✦, whose label sequence lists these node labels in preorder✦ and whose core tree degree sequence lists their arities.✦ For an ordered tree of cores , the maximum core degree is the largest core length appearing in ( if is a leaf)✦, and inserting child subwords into the corners of each core maps ordered trees of cores bijectively to stack-emptying typed words.✦
For and , the core generating polynomial coefficient sums over connected typed cores of length ✦, the block generating polynomial coefficient is ✦, and the actual FK block mass under is .✦ A critical even offspring distribution is a probability mass function on supported on even integers with , , mean , and finite variance (with standard deviation ).✦ Doubling block offspring probability weights via on even and on odd produces a critical even offspring distribution whenever , , , and ✦; applying this construction to yields the critical FK corner offspring law (with standard deviation ).✦ The doubled block mass sequence of a sequence evaluates at to when is even, and to zero otherwise.✦
For an inventory FK model parameter tuple , the root core mark distribution on optional core labels is the probability distribution assigning weight to the empty label and to each connected typed core .✦ For an inventory FK model parameter tuple and , the conditional core mark distribution is the probability distribution on optional core labels of arity obtained by conditioning the root core mark distribution on labels of arity (taking the point mass at the empty label when no label has arity ).✦
Marked Tree Codes, Height Paths, and Spine Sums
For a sequence , its total step is ✦ and its degree sequence partial walk at step is .✦ A discrete bridge sequence of length is a map from to with ✦, and a Lukasiewicz tree code of length is a discrete bridge sequence satisfying for all (equivalently, the degree increment word satisfies the discrete excursion condition of summing to with all proper prefix sums nonnegative). A compatible marked tree code of length is a pair consisting of a Lukasiewicz tree code of length and an assignment of an optional core label to each satisfying .✦ For a compatible marked tree code of length , the reconstructed core tree is the ordered tree of cores reconstructed from ✦, and the associated rooted planar map is the planar map underlying the tree-decorated rooted map of size obtained from via the core-tree and rooted-map word bijections. A marked tree code sample of size is a pair consisting of a Lukasiewicz tree code of length and any assignment of optional core labels on .✦
Given a critical even offspring distribution and , conditioning the i.i.d. product measure on total step produces the conditioned offspring bridge law✦, and pushing this law forward under cyclic rotation by the unique index achieving the minimum prefix sum to form a valid tree code defines the conditioned tree code law on Lukasiewicz tree codes of length .✦ Given a critical even offspring distribution , , and a mark kernel , the marked tree code law is the probability distribution on pairs obtained by sampling a Lukasiewicz tree code of length from the conditioned tree code law and assigning independent node marks distributed according to at each index .✦ For an inventory FK model parameter tuple and , the law of marked code draw on marked tree code samples of size is the marked tree code law specialized to , , and .✦
For a degree sequence of length and a step , the tree vertex height is the number of indices (with ) such that for every with .✦ Given a sequence of real numbers, its piecewise-linear interpolation on is ✦, where is the interpolation hat function.✦ For a critical even offspring distribution with standard deviation and a Lukasiewicz tree code of length , the normalized preorder height path is the piecewise-linear interpolation of for .✦ For an inventory FK model parameter tuple and a marked tree code sample of size , the actual tree height path is the rescaled path on .✦ For a nonnegative integer , the height scaling factor is .✦
Given a Lukasiewicz tree code of length and a step , reversing the prefix of length gives the stream with for and for , whose partial walk is . The spine records of at step are the weak ascending record times where for all ✦; each record corresponds to the spine vertex and carries the spine record type . For a pair and an optional core label , the core label metric increment is the real number equal to when is a connected typed core with and , and equal to otherwise.✦ For a Lukasiewicz tree code of length , an assignment of optional core labels, and a step , the marked spine sum is defined by (5): (5)✦
For an infinite sequence in , the offspring walk partial sum is ✦, and the ladder epoch condition holds at index if or if for all and .✦ For an infinite sequence in , the first weak ascending ladder epoch is the smallest index satisfying the ladder epoch condition✦, the weak ladder overshoot of is ✦, and the spine ladder variable pair of is .✦ For a critical even offspring distribution , the offspring spine ladder distribution on is the pushforward of the infinite i.i.d. product measure under the spine ladder variable pair.✦ For an inventory FK model parameter tuple , the mean core metric increment is the integral of first against and then against .✦
For an inventory FK model parameter tuple and , the CRT scaling constant is ✦ and the edge metric rescaling factor is .✦ For an inventory FK model parameter tuple , , and , the bad metric event is the set of all marked tree code samples of size satisfying at least one of three conditions: (i) for some ; (ii) for all and ; or (iii) for some .✦ For a scale factor , size , and bounded continuous GHP test , the marked tree map test observable is the real-valued function on marked tree code samples of size defined by if for all , and otherwise.✦
The Claim
Theorem 1.
Let be a critical even offspring distribution with standard deviation , let , and let be a compatible marked tree code of length with reconstructed core tree and rooted planar map . Let with and , and set for . Suppose that for every , that whenever satisfy , and that . Then the GHP bound (6) holds: (6)✦
Given FK model parameters , , a compatible marked tree code of length with core tree and rooted planar map , a continuous function , and real numbers with , suppose that for every , that , that whenever satisfy , and that . Then the nearby path comparison (7) gives: (7)✦
Given FK model parameters , a bounded continuous GHP test , a real number , and a continuous function , there exist , , and such that for every and every marked tree code sample of size whose height path satisfies , the observable error satisfies (8): (8)✦
Given FK model parameters , a probability space carrying three independent Brownian motions , and a bounded continuous GHP test , the marked map test expectations follow (9): (9)✦
For every Potts parameter , there exists a scaling constant such that on every probability space carrying three independent Brownian motions and for every bounded continuous GHP test , the finite FK map expectations converge according to (10): (10)✦
In the paper, the result reads: rescaled map metric comparison with the exploration walk excursion metric , correspondence between map vertices and excursion tree points, coupling of measures via uniform time, and convergence to , where stands for and for .
What Is Checked
The five claims are stated over rooted planar maps with edges (as equivalence classes of fixed-point-free dart involutions and vertex rotations of genus zero), the FK cluster measure at Potts parameter , GHP distance via isometric amalgamations, bounded continuous GHP test functionals on compact metric probability spaces, and the Brownian CRT constructed from the three-dimensional Bessel bridge of three independent Brownian motions. On the coding side, they are stated over critical even offspring distributions arising from FK block offspring weights, compatible marked tree codes and their ordered trees of connected typed cores, the law of marked code draw, normalized and actual tree height paths, marked spine record sums, the mean core metric increment, the edge metric rescaling factor, the marked tree map test observable, and the bad metric event.
For the underlying constructions, conjugating a labelled planar map by any dart permutation preserves the planar map conditions✦, and partially reversing darts on an edge-orbit subset yields an involution.✦ Numbering darts along a single-cycle tour from the root dart is bijective.✦
Every stack-emptying typed word admits disjoint non-crossing arch matchings for the two burger types covering all its positions.✦ For an ordered tree of cores, its core tree degree sequence satisfies the discrete excursion condition✦ and core tree reconstruction from a compatible marked code of length preserves the label length .✦ Every sequence in admits a time satisfying the ladder epoch condition.✦ Under any FK model parameters , the actual FK block masses are nonnegative at all sizes✦ and strictly positive at sizes and .