The Setting
Take a finite tree with vertex set , nonnegative lengths on its edges, its path distance , and a probability distribution on . Let , and be independent random vertices with law . The mean measures how much the distance from changes when is replaced by an independent copy . The question is how large it must be, compared with the total length of the tree, when every edge of positive length splits into two sides that both carry a substantial part of the mass of .
Root the tree at a vertex and give each edge the vertex set of the subtree below it. Any two of these sets are nested or disjoint, and is the total length of the edges whose set contains exactly one of and . The library states the lemma for any such family of subsets of with lengths on its members.
Laminar Families and Cut Distances
A family of subsets of a finite set is laminar if any two of its members are nested or disjoint: (1)✦
The indicator of a subset of is the function on equal to on and to off .✦
The cut distance of a family of subsets of , with a real length given to each subset of , is the function on pairs of points of given by (2)✦ The members of are called cuts.
The mass of a subset of under a real function on is .✦
The Claim
Theorem 1. Let be a laminar family of subsets of a finite set , let give each subset of a real length with for every , and let be the cut distance (2) of with lengths . Let be a probability distribution on and a real number such that every cut of positive length has mass . Then for independent random points , , of with law , (3)✦
In the paper, the result reads: if a finite tree has nonnegative edge lengths summing to , path pseudometric and a probability distribution on its vertices, and every edge of positive length separates two vertex sets each of -mass at least , where , then independent , , of law satisfy .
What Is Checked
The claim (3) is stated over a laminar family of subsets of a finite set , lengths nonnegative on its cuts, the cut distance (2) built from the indicators , and a probability distribution on through the masses of the cuts.