Unions of random trees and applications

Abstract In 1986, Janson showed that the number of edges in the union of k random spanning trees in the complete graph K n is a shifted Poisson distribution. Using results from the theory of electrical networks, we provide a new proof of this result, and we obtain an explicit rate of convergence. This rate of convergence allows us to show a new upper tail bound on the number of trees in G ( n , p ) , for p a constant not depending on n . The number of edges in the union of k random trees is related to moments of the number of spanning trees in G ( n , p ) . As an application, we prove the law of the iterated logarithm for the number of spanning trees in G ( n , p ) . More precisely, consider the infinite random graph G ( N , p ) , with vertex set N and where each edge appears independently with constant probability p . By restricting to { 1 , 2 , … , n } , we obtain a series of nested Erdős–Reyni random graphs G ( n , p ) . We show that a scaled version of the number of spanning trees satisfies the law of the iterated logarithm.