Tree and forest weights and their application to nonuniform random graphs (Q1296594)

The tree-weight of a complete \(n\)-graph with weighted edges is the sum, over all spanning trees of the graph, of the products of the weights of the edges in the trees. The authors show that on the set of edge-weight distributions of given total weight, the tree-weight function attains its maximum at the uniform distribution; they also establish an analogous result with respect to the weights of the spanning rooted \(k\)-forests. Their results lead to the conclusion that the number of trees in a random rooted forest can be represented as a sum of \(n\) independent Bernoulli random variables where the success probabilities of the variables can be expressed in terms of the eigenvalues of the Kirchhoff matrix corresponding to the edge weights. The authors also apply their results to investigate the probability that a realisation of a certain sparse random graph model is a spanning tree.