<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
The Edge Correlation of Random Forests
Dudley Stark
School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United Kingdom
Annals of Combinatorics 15 (3) pp.529-539 July, 2011
AMS Subject Classification: 05C05, 05C80
The conjeture was made by Kahn that a spanning forest F chosen uniformly at random from all forests of any finite graph G has the edge-negative association property. If true, the conjecture would mean taht given any two edges ε1 and ε2 in G , the inequality P(ε1F, ε2F)≤P(ε1F)≤(ε2F)would hold. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices. We derive explicit related results for random trees.
Keywords: random tree, random forest, edge-negative association property


1. Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discrete Math. 3(2), 216–240 (1990)

2. Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)

3. Grimmett, G.R., Winkler, S.N.: Negative association in uniform forests and connected graphs. Random Structures Algorithms 24, 444–460 (2004)

4. Kahn, J.: A normal law for matchings. Combinatorica 20(3), 339–391 (2000)

5. Moon, J.W.: Counting Labelled Trees. Canadian Mathematical Monographs, Montreal, Que. (1970)

6. Pemantle, R.: Towards a theory of negative dependence. J. Math. Phys. 41(3), 1371–1390 (2000)

7. Rényi, A.: Some remarks on the theory of trees. Magyar Tud. Akad. Mat. Kutató Int. Közl. 4, 73–85 (1959)

8. Semple, C.,Welsh, D.J.A.: Negative correlation in graphs and matroids. Combin. Probab. Comput. 17(3), 423–435 (2008)

9. Seymour, P.D.,Welsh, D.J.A.: Combinatorial applications of an inequality from statistical mechanics. Math. Proc. Cambridge Philos. Soc. 77, 485–495 (1975)

10. Weinberg, L.: Number of trees in a graph. Proc. IRE 46, 1954–1955 (1958)