2025/01/30 by Miklós Bóna, Bona, Miklos, Burghart, Fabian +1
Computer Science · #Graph Labeling and Dimension Problems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2501.18570
We consider the number of common edges in two independent random spanning trees of a graph G. For complete graphs Kn, 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+\gep. We also use the same method to prove an analogous result for complete multipartite graphs.