On the intersection of pairs of trees
read the original abstract
We consider the number of common edges in two independent random spanning trees of a graph $G$. For complete graphs $K_n$, we give a new proof of the fact, originally obtained by Moon, that the distribution converges to a Poisson distribution with expected value $2$. This is applied to show a Poisson limit law for the number of common edges in two independent random spanning trees of an Erd\H{o}s--R\'enyi random graph $G(n,p)$ for constant~$p$. We also use the same method to prove an analogous result for complete multipartite graphs.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Intersecting Families of Spanning Trees of $K_{n,n}$
For large n and t up to n over C log n, the maximum t-intersecting families of spanning trees in K_{n,n} consist of all trees containing a fixed t-matching plus a negligible number of exceptions.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.