Negative association in uniform forests and connected graphs

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.

With minor corrections

References in corpus (1)

• The Random-Cluster Model

Cited by in corpus (7)

• On combinatorial testing problems
• On the number of forests and connected spanning subgraphs
• The Component Graph of the Uniform Spanning Forest: Transitions in Dimensions $9,10,11,\dots$
• Elementary proof of Rayleigh formula for graphs
• A strong log-concavity property for measures on Boolean algebras
• Negative correlation and log-concavity
• Sums of squares and negative correlation for spanning forests of series parallel graphs