We have developed a theory for trees analogous to the seminal work of Borgs, Chayes, Lovasz, Sos, Szegedy and Vesztergombi. We propose the following simple procedure for sampling: uniformly select k edges of the tree and form the sample by contracting all other edges. The sampling procedure naturally defines a local distance on finite trees.
We introduce a global distance similar to the Frieze-Kannan cut-distance for dense graphs and prove that the two distances are equivalent (like in the case of dense graphs).
The natural limit objects are certain compact real trees equipped with an additional probability measure. These are well studied objects (Aldous, Evans, Winter and others) and form a separable compact space with respect to the Wasserstein metric, which coincides with the global metric mentioned above. Sampling real trees can be naturally defined and we prove that a sampling sequence of finite trees of increasing size converges to the original real tree with probability one.
(joint work with Gabor Elek)
Copyright. All Rights Reserved.