Tree and forest weights and their application to nonuniform random graphs

For a complete graph K-n on n vertices with weighted edges, define the weig ht of a spanning tree (more generally, spanning forest) as the product of e dge weights involved. Define the tree weight (forest weight) of K-n as the total weight of all spanning trees (forests). The uniform edge weight distr ibution is shown to maximize the tree weight, and an explicit bound on the tree weight is formulated in terms of the overall variance of edge weights as well as the variance of the sum of edge weights over nodes. An applicati on to sparse random graphs leads to a bound for the relative risk of observ ing a spanning tree in a well-defined neighborhood of the uniform distribut ion. An analogous result shows that, for each positive integer it, the weig ht of all forests with k rooted trees is also maximized under the uniform d istribution. A key ingredient for the latter result is a formula for the we ight of forests of k rooted trees that generalizes Maxwell's rule for spann ing trees. Our formulas also enable us to show that the number of trees in a random rooted forest is intrinsically divisible, that is, representable a s a sum of n independent binary random variables epsilon(j), with parameter (1 + lambda(j))(-1), lambda's being the eigenvalues of the Kirchhoff matri x. This is directly analogous to the properties of the number of blocks in a random set partition (Harper), of the size of the random matching set (Go dsil) and of the number of leaves in a random tree (Steele).