The Setting
Finite ordered trees organize integer windows into descendant blocks. A window attached to an edge is a finite interval of integer indices, and the order of the children determines a depth-first preorder of the edges.
Fix nonnegative integers and . The child alphabet for a tree with nondefault children is the finite set in (1); is the default choice, and the indices less than are the nondefault choices: (1)✦ The set of decision nodes is the set of paths over of length less than , as in (2); the empty path is the root: (2)✦ The set of terminal paths is the set of paths over of length exactly , as specified by (3): (3)✦ The total number of children is ; the window construction below uses as its branching parameter.
For a general nonnegative integer , write . An edge of the complete ordered tree of depth is a nonempty path over with .✦ Its height is given in (4): (4) Write when is a prefix of , and for a proper prefix. The notation appends a child to , and appends followed by a path .
Fix nonnegative integers and . A separated window system is a sequence of nonnegative integer lengths and nonnegative integer endpoints satisfying (5); the conditions involving paths apply whenever the displayed edge paths belong to : (5)✦ The edge window is the integer interval in (6): (6)✦ The global index set is the union in (7): (7)✦
Recursive Spans
The recursive window length is the sequence in (8), defined together with the complete tree span in (9): (8)✦ (9)✦ Here uses natural subtraction when . The child span , comprising an incoming window and the subtree below it, is defined by (10): (10)✦
Preorder Placement
Depth-first preorder lists each child edge before its descendants, completing the children in increasing order.✦ Let be the number of edges, and let be this list of edges. The edge preorder rank starts at zero✦; the vertex preorder rank assigns zero to the root and to a nonempty path .✦
The prescribed preorder length list and its zero extension are given in (11): (11) The starting index and endpoint at preorder position are defined by (12), with subtraction in the natural numbers: (12)
The Claim
Theorem 1. Let be a real number with . There are positive integers meeting the probability budgets in (13), for every natural number and every natural number : (13)✦ For arbitrary nonnegative integers , the recursive child span satisfies (14): (14)✦ For every , and nonnegative integers , the assignments in (15) define a separated window system: (15)✦
In the paper, the result reads: for , choose and with and , take the complete ordered -ary tree of depth with edges in preorder, choose with and such that for every integer , set , for , and for , and place in preorder starting at with unused indices between consecutive windows and , so that the largest endpoint in the child block beginning at an edge of height satisfies .
What Is Checked
The statements concern finite paths in complete ordered trees, nonnegative integer gaps and thresholds, and real parameters ; the window conditions in (5) apply to valid edges and the specified prefix and sibling pairs.