Negative association in uniform forests and connected graphs

DOI10.1002/RSA.20012zbMATH Open1048.60007arXivmath/0302185OpenAlexW2949117595MaRDI QIDQ4739581FDOQ4739581

Authors: G. R. Grimmett, S. N. Winkler 

Publication date: 6 August 2004

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We consider three probability measures on subsets of edges of a given finite graph $G$, namely those which govern, respectively, a uniform forest, a uniform spanning tree, and a uniform connected subgraph. A conjecture concerning the negative association of two edges is reviewed for a uniform forest, and a related conjecture is posed for a uniform connected subgraph. The former conjecture is verified numerically for all graphs $G$ having eight or fewer vertices, or having nine vertices and no more than eighteen edges, using a certain computer algorithm which is summarised in this paper. Negative association is known already to be valid for a uniform spanning tree. The three cases of uniform forest, uniform spanning tree, and uniform connected subgraph are special cases of a more general conjecture arising from the random-cluster model of statistical mechanics.

Full work available at URL: https://arxiv.org/abs/math/0302185

Recommendations

• Edge-negative association in random spanning forests and connected subgraphs on connected finite graphs
• Negative Correlation in Graphs and Matroids
• The edge correlation of random forests
• scientific article; zbMATH DE number 1195780
• scientific article; zbMATH DE number 953290

zbMATH Keywords

negative associationuniform spanning treeuniform connected graphuniform forest

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05)

Cites Work

• Percolation
• Probability on trees and networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs

Cited In (19)

• On combinatorial testing problems
• Correlated Matroids
• Lorentzian polynomials
• Some inequalities for Whitney-Tutte polynomials
• Random spanning forests and hyperbolic symmetry
• Edge-negative association in random spanning forests and connected subgraphs on connected finite graphs
• Loop-erased partitioning via parametric spanning trees: monotonicities \& 1D-scaling
• The component graph of the uniform spanning forest: transitions in dimensions \(9,10,11,\ldots\)
• Negative Correlation in Graphs and Matroids
• Upper bound for the number of spanning forests of regular graphs
• Connectivity in random forests and credit networks
• On the number of forests and connected spanning subgraphs
• Negative correlation and log-concavity
• A combinatorial proof of the Rayleigh formula for graphs
• Evaluations of Tutte polynomials of regular graphs
• Uniqueness of the infinite tree in low-dimensional random forests
• Negative dependence and Srinivasan's sampling process
• The edge correlation of random forests
• A strong log-concavity property for measures on Boolean algebras

This page was built for publication: Negative association in uniform forests and connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4739581)