The Setting
For random planar maps weighted by Fortuin-Kasteleyn percolation with cluster weight , the partition function of maps decorated by spanning trees can be computed through a bijection with words in an inventory alphabet. The inventory processes burgers and orders along a stack. An inventory word is empty-reducing when its execution consumes all burgers and satisfies all orders, leaving an empty stack. The central identity equates the probability that an independent inventory word of length is empty-reducing to , where is the partition coefficient of maps with edges and is the inventory radius with . These notes go through that identity, the map-word bijection, and the definitions they are built on.
Planar Maps and Spanning Trees
A dart of size is an element of the finite set indexing the directed edges of a map with edges.✦ An orbit of a dart under a permutation of is the equivalence class of under the cyclic subgroup generated by ✦, and the orbit set is the set of all such orbits.✦ The spanning subgraph associated with permutations and on and a set of edge orbits is the simple graph with vertex set and an undirected edge between and whenever there exists a dart with , , and .✦ The unordered endpoints of an edge orbit under permutations and are the vertex orbits for any representative dart .✦
A pair of permutations on satisfies the planar map conditions if is a fixed-point-free involution, the spanning graph is connected, and the orbit counts satisfy the genus zero relation (1)✦ A labelled planar map of size is a pair of permutations on satisfying the planar map conditions.✦ An isomorphism of rooted maps between labelled planar maps and of size is a permutation of fixing the root dart such that and .✦ A rooted planar map of size is an isomorphism class of labelled planar maps of size under root-preserving isomorphism.✦ For a rooted planar map of size represented by permutations , the dart reversal involution is the permutation swapping opposite darts✦, the vertex rotation permutation is the permutation cyclically ordering darts around each vertex✦, and the edge set is the set of dart orbits under .✦
A multiforest for permutations on is a subset of edge orbits such that the spanning subgraph is acyclic without self-loops and edge endpoints are injective on .✦ The spanning tree completions of an edge subset within an edge subset for permutations on are the collection of all edge subsets extending to a spanning tree of the map within .✦ A tree-decorated rooted map of size is a pair consisting of a rooted planar map of size and a spanning tree of edges of .✦ For an involution on and an edge subset , the partial dart reversal is the permutation of that swaps and when and fixes otherwise.✦
The loop polynomial of a rooted planar map of size at parameter is the sum over edge subsets (2)✦ where is the partial dart reversal along . The rooted map partition function is defined by and, for each integer , by the sum of loop polynomials (3)✦ where is the collection of all rooted planar maps of size . For an edge subset , the submap component count is the number of connected components of the spanning subgraph .✦ For a parameter , permutations and on , and edge subsets , the residual configuration weight is (4)✦ The residual partition function is the sum of residual weights (4) over all subsets : (5)✦
A canonical rooted tree map of size is a triple where satisfies the planar map conditions (1) and the edge subset forms a spanning tree such that the tree tour equals the standard cyclic permutation on .✦ For any permutation of consisting of a single cycle, the root tour numbering permutation is the permutation of defined by .✦ The canonicalization to tree normal form is the map sending a labelled planar map and a spanning tree of edges to a canonical rooted tree map by relabelling darts along the tour.✦ The rooted spanning tree canonical bijection is the bijection mapping each tree-decorated rooted map of size to its canonical rooted tree map in canonical normal form.✦ For a dart permutation of , the permutation conjugation is the map sending a permutation to ✦, and the orbit relabelling equivalence is the induced bijection between and .✦ For a dart permutation of , the relabelling of an edge subset under an involution is the edge subset under obtained by pushforward along the inverse of the orbit relabelling equivalence.✦
Inventory Words and Stack Evaluation
An inventory order type is an element of the set , where represents an order satisfied by either burger type.✦ An inventory alphabet letter is either a burger of boolean type or an inventory order type.✦ A typed burger-order letter is either a burger of boolean type or a fixed order of boolean type .✦ An inventory stack evaluation state is a pair consisting of a list of pending orders and a list of available burgers stored freshest-first.✦ The evaluation of a word is the transition map on inventory stack evaluation states obtained by processing letters sequentially, pushing each burger onto the burger stack, and letting each order consume the freshest eligible burger or join the pending orders when no match is available.✦ The word reduction is the evaluation state obtained by processing a word starting from empty stacks.✦ A word of alphabet letters is empty-reducing if .✦
The Fortuin-Kasteleyn parameter is for ✦, with inventory radius .✦ The letter mass function assigns to each letter probability to each burger type, to the flexible order, and to each fixed order type: (6)✦ The letter distribution is the probability measure on the inventory alphabet with masses given by (6)✦, and the inventory stream measure is the infinite product measure of the letter distribution on infinite sequences of letters.✦ The letter stream initial word of length is the prefix consisting of the first letters of an inventory stream.✦ The empty-reducing word probability is the probability under the inventory stream measure that the initial word of length is empty-reducing.✦
The canonical tour matching word of an involution on and an edge subset is the sequence of typed letters defined on darts by (7)✦ The typed word stack execution is the evaluation map sending a sequence of typed letters and a boolean burger stack to an updated stack upon successful matching or failure upon illegal closure.✦ A successful dart word of size is an assignment from to typed letters whose typed stack execution across the standard dart order empties the boolean stack, with denoting the set of all such words.✦ The canonical tree tour word of a canonical rooted tree map is the successful dart word defined by (7).✦ The canonical tree word equivalence is the bijection between canonical rooted tree maps of size and successful dart words in given by the tour matching word.✦ The rooted map-word bijection is the composite bijection identifying tree-decorated rooted maps of size with successful dart words in .✦ The flexible closing count is the number of flexible order closures encountered when evaluating a typed word against an initially empty boolean stack.✦
The Claim
Theorem 1. Let , , , and . For every integer , the inventory identity holds: (8)✦ For every integer , the empty-reducing word probability is given by the Fortuin-Kasteleyn sum (9)✦ For every and every function , the weighted pushforward to words satisfies (10)✦ Here is the set of successful dart words of size , is the underlying rooted map of the tree-decorated map , and is the flexible closing count. For permutations and on with an involution, finite subsets of edge orbits and , and an edge orbit whose endpoints are disconnected in the spanning subgraph , the residual partition function satisfies the deletion-contraction recurrence (11)✦ For an integer , any fixed-point-free involution on , and any function constant on orbits of without monochromatic crossings, the flexible closing count of the matching word equals the outer chord count (12). (12)✦
In the paper, the result reads: for every integer , an independent word of length satisfies .
What Is Checked
The identities (8) and (9) are stated over the Potts parameter and the inventory stream measure. The transport formula (10) is stated over rooted planar maps and successful dart words, the deletion-contraction recurrence (11) over dart permutations and confirmed forests, and the chord identity (12) over non-crossing involutions.
The library establishes that dart relabelling preserves the planar map conditions✦, that partial dart reversal is an involution✦, that cycle tour numbering is bijective✦, and that the canonical normal form of tree-decorated rooted maps is a bijection.✦