Unions of random trees and applications

DOI10.1016/J.DISC.2020.112265zbMATH Open1456.05032arXiv1701.06208OpenAlexW3114195415MaRDI QIDQ2222962FDOQ2222962

Authors: Austen James, Matt Larson, Daniel Montealegre, Andrew Salmon 

Publication date: 27 January 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

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(mathbbN,p)$, with vertex set $mathbbN$ and where each edge appears independently with constant probability $p$. By restricting to $1,2,dotsc,n$, we obtain a series of nested Erd"{o}s-R'{e}yni random graphs $G(n,p)$. We show that a scaled version of the number of spanning trees satisfies the law of the iterated logarithm.

Full work available at URL: https://arxiv.org/abs/1701.06208

Recommendations

• Random trees in a graph and trees in a random graph
• scientific article; zbMATH DE number 953290
• Growth of the Number of Spanning Trees of the Erdős–Rényi Giant Component
• Tree and forest weights and their application to nonuniform random graphs
• On the probability that a random subtree is spanning

zbMATH Keywords

law of iterated logarithmelectrical networkrandom spanning treedinner table problemErdős-Renyi random graph

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Cites Work

• Probability on trees and networks
• When are small subgraphs of a random graph normally distributed?
• On the maximum degree in a random tree
• Title not available (Why is that?)
• Spanning Subgraphs of Random Graphs
• An upper bound for the number of spanning trees of a graph
• Title not available (Why is that?)
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• Random trees in a graph and trees in a random graph
• Intersections of randomly embedded sparse graphs are Poisson
• Law of the iterated logarithm for random graphs

Cited In (4)

• Random ultrametric trees and applications
• Growth of the Number of Spanning Trees of the Erdős–Rényi Giant Component
• Some Wellfounded Trees in UniMath
• Random trees in a graph and trees in a random graph

This page was built for publication: Unions of random trees and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2222962)