Loop-erased partitioning via parametric spanning trees: Monotonicities & 1D-scaling

Stochastic Processes and their Applications, vol. 176, pp. 104436

Abstract

We consider a parametric version of the UST (Uniform Spanning Tree) measure on arbitrary directed weighted finite graphs with tuning (killing) parameter q>0. This is obtained by considering the standard random weighted spanning tree on the extended graph built by adding a ghost state † and directed edges to it, of constant weights q, from any vertex of the original graph. The resulting measure corresponds to a random spanning rooted forest of the graph where the parameter q tunes the intensity of the number of trees as follows: partitions with many trees are favored for q>1, while as q→0, the standard UST of the graph is recovered. We are interested in the behavior of the induced random partition, referred to as Loop-erased partitioning, which gives a correlated cluster model, as the multiscale parameter q∈[0,∞) varies. Emergence of giant clusters in this correlated percolation model as a function of q has been recently explored on certain dense growing graphs Avena et al. (2022). Herein we derive two types of results. First, we explore monotonicity properties in q of this forest measure on general graphs showing in particular some counter-intuitive subtleties in non-reversible settings where the electrical-network interpretation of the UST observables gets partially lost. Second, by analyzing 2-points correlations on trees and various very sparse growing graph models, we characterize emerging macroscopic clusters, as q scales with the graph size, and derive related phase diagrams.

Authors 3

1. Luca Avena corresponding

   University of Florence

   Affiliation as printed

   University of Florence, DIMAI, Viale Giovanni Battista Morgagni, 67/a, 50134, Firenze, Italy

2. Jannetje Driessen Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Leiden University, Mathematical Institute, Einsteinweg 55, 2333 CC, Leiden, The Netherlands

3. Twan Koperberg Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Leiden University, Mathematical Institute, Einsteinweg 55, 2333 CC, Leiden, The Netherlands