2003/02/17 by Geoffrey Grimmett, G. R. Grimmett, Severin Winkler +3 · 2 citations
Computer Science · Mathematics · #05C80 #60C05 #82B20 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #math.CO #math.PR #msc:05C80 #msc:60C05 #msc:82B20
paper · pdf · doi:10.48550/arxiv.math/0302185
With minor corrections
openalex publication_date 2003/02/17 · arxiv created 2003/02/24 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.