Negative association in uniform forests and connected graphs | Zendy

Grimmett G. R. | Zendy; Winkler S. N. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Negative association in uniform forests and connected graphs

Author(s) -

Grimmett G. R.,

Winkler S. N.

Publication year - 2004

Publication title -

random structures and algorithms

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.314

H-Index - 69

eISSN - 1098-2418

pISSN - 1042-9832

DOI - 10.1002/rsa.20012

Subject(s) - combinatorics , conjecture , mathematics , spanning tree , random graph , kruskal's algorithm , graph factorization , minimum spanning tree , tree (set theory) , vertex connectivity , discrete mathematics , graph , graph power , line graph , vertex (graph theory)

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 18 edges, using a certain computer algorithm which is summarized 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. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research