×

Uniform and minimal essential spanning forests on trees. (English) Zbl 0895.60099

Let \(G\) be a finite undirected connected graph with vertex set \(V\) and edge set \(E\). Let \({\mathcal T}_G\) denote the set of all spanning trees for \(G\). There are two natural probability measures on \({\mathcal T}_G\): Let \(\mu_G\) denote the uniform distribution on \({\mathcal T}_G\). A second choice is \(\nu_G\) which is obtained as follows: Let \(X_e\) \((e\in E)\) be independent random variables each having a uniform distribution on \([0,1]\). Then pick \(T\in{\mathcal T}_G\) if \(T\) minimizes the sum of all \(X_e\) \((e\in T)\). The corresponding random graphs are called uniform resp. minimal spanning trees. R. Pemantle [Ann. Probab. 19, No. 4, 1559-1574 (1991; Zbl 0758.60010)] and K. S. Alexander [ibid. 23, No. 1, 87-104 (1995; Zbl 0827.60079)] have shown how \(\mu_G\) and \(\nu_G\) can be generalized in the case \(G= Z^d\) \((d\geq 2)\). The resulting random graphs are called uniform resp. minimal essential spanning forests (UESF resp. MESF). The purpose of the present paper is to define and investigate the corresponding objects when \(G\) is replaced by an infinite locally finite tree rather than by \(Z^d\). In particular, it is shown that the UESF measure arises as a limit of random-cluster measures. Despite some similarities between the UESF and MESF measures it turns out (cf. Theorem 4.5) that they are not equal. The construction of the MESF measure is motivated e.g. by J. T. Chayes, L. Chayes and C. M. Newman [Commun. Math. Phys. 101, 383-407 (1985)] and C. M. Newman and D. L. Stein [J. Stat. Phys. 82, 1113-1132 (1996)].

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI