Tree and forest weights and their application to nonuniform random graphs
type: Item
instance of: scholarly article
title: Tree and forest weights and their application to nonuniform random graphs
zbMATH Open document ID: 0930.05031
author: Brian D. Jones
author: Boris Pittel
author: Joseph Verducci
published in: The Annals of Applied Probability
publication date: 2000-02-09T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 1319824
zbMATH Keywords: Maxwell's rule
zbMATH Keywords: spectral graph
zbMATH Keywords: tree polynomial
zbMATH Keywords: spanning trees
zbMATH Keywords: total weight
zbMATH Keywords: tree-weight function
zbMATH Keywords: random rooted forest
zbMATH Keywords: eigenvalues
zbMATH Keywords: Kirchhoff matrix
zbMATH Keywords: sparse random graph model
reviewed by: J. W. Moon
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1029962602
OpenAlex ID: W2068381506
cites work: Poisson convergence and random graphs
cites work: Exponential models for directional data
cites work: Q4770409
cites work: Q3682518
cites work: Cliques in random graphs
cites work: Q5691133
cites work: A combinatorial Laplacian with vertex weights
cites work: Q3999383
cites work: Q3267900
cites work: Q3909070
cites work: Random Graphs
cites work: Matching behaviour is asymptotically normal
cites work: Q3216703
cites work: Q3137758
cites work: An upper bound for the number of spanning trees of a graph
cites work: On colouring random graphs
cites work: A bound for the complexity of a simple graph
cites work: Stirling Behavior is Asymptotically Normal
cites work: Theory of monomer-dimer systems
cites work: The birth of the giant component
cites work: A normal law for matchings
cites work: Q4871754
cites work: Asymptotic Formulas for the Probability of k-Connectedness of Random Graphs
cites work: The Structure of a Random Graph at the Point of the Phase Transition
cites work: Inequalities: theory of majorization and its applications
cites work: Monotonicity of permanents of doubly stochastic matrices
cites work: Q5616724
cites work: Q3680834
cites work: Probabilistic bounds on the coefficients of polynomials with only real zeros
cites work: On tree census and the giant component in sparse random graphs
cites work: Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees
cites work: Combinatorial Algebra and Random Graphs
cites work: Q4002255
DOI: 10.1214/AOAP/1029962602
description: scientific article; zbMATH DE number 1319824