The Setting
The finite graph construction compares walks with label sequences subject to vertex compatibility and transition relations. A root is counted when some walk from it has no immediate reversal and admits such a sequence. Let and be finite sets of generators and colors, and let be a finite label set. Write for the free group on , identifying each generator with its canonical image in . The signed ports, their reversal and their associated group elements are given by (1). (1)
A graph with reversible ports on a vertex set consists of a reversal map and a move map satisfying (2). (2)✦
For a nonnegative integer , the word ball in is the set of group elements of reduced length at most , and its word ball permutation group is the group of permutations of , as in (3). (3) For a generator , an extended generator translation is a permutation of that agrees with left multiplication by whenever the product remains in . Choose one for each . The word ball permutation representation is the homomorphism from to determined by these choices; (4) also specifies the moves of the finite Cayley graph. (4)
The all-colorings graph has vertex set : a vertex consists of a coloring of and a group element . Its move keeps the coloring fixed, and its root color is , as specified in (5). (5) The sequence graph is the disjoint union of the graphs over all radii.✦ Its vertex set , the inclusion of a radius and its componentwise coloring are given by (6); moves stay at the same radius. (6)
Matching Rules
Fix a graph with reversible ports, a compatibility relation between vertices and labels in , and a transition relation on . For a port word starting at , let be its successive vertices. A port word in a graph with reversible ports is reduced, or nonbacktracking, when it satisfies the first condition in (7); a walk with initial label in is matched when it satisfies the second condition. (7) A root of a graph with reversible ports is good to depth when no reduced matched walk of length starts at . The set of bad roots of a graph with reversible ports consists of the roots that are not good to depth , as in (8), with the matching relations understood. (8)
A palette assignment on is a map that assigns to each label a subset . The palette width and the transition bound are nonnegative integers satisfying (9). (9)
The Claim
Theorem 1. Let be nonnegative integers. Suppose the palettes and transitions satisfy (9), and compatibility on requires whenever . The finite counting bound is (10). (10)✦ Suppose instead that compatibility is specified on and requires whenever , with the same palette and transition bounds. Assume and . For every nonnegative integer , there is an integer satisfying (11). (11)✦
In the paper, the result reads: for fixed , if is the fraction of vertices of starting a matched walk of length , then , and consequently one can first choose and then with .
What Is Checked
The claims are stated over finite colorings of word ball permutation groups, compatibility relations constrained by palettes, and label transitions with at most successors. The generator translation extension theorem ensures that an extended generator translation exists for every radius and every generator .✦