Unions of random trees and applications

DOI10.1016/J.DISC.2020.112265MaRDI QIDQ2222962zbMATH OpenOpenAlexFDO

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

Publication date 27 January 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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)