Answers are grounded in this paper and cite their sources.
Probabilistic analysis reveals Poisson and normal limit distributions for shared edges in random spanning trees, indicating universal asymptotic overlap behavior across graph classes.
We consider the number of common edges in two independent random spanning trees of a graph G. For complete graphs Kₙ, 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ős--Rényi random graph $G(n,p)$ for constant~p, as well as a central limit theorem in the case where p→ 0 and p≥ n-2/3+. We also use the same method to prove an analogous result for complete multipartite graphs.
No takes yet. Share an insight, caveat, or question.
Miklós Bóna (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: