2013/08/21 by Chin, Alex J., Gordon, Gary, MacPhee, Kellie J. +1
#05C80 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1308.4613
We study the asymptotic behavior of four statistics associated with subtrees of complete graphs: the uniform probability pn that a random subtree is a spanning tree of Kn, the weighted probability qn (where the probability a subtree is chosen is proportional to the number of edges in the subtree) that a random subtree spans and the two expectations associated with these two probabilities. We find pn and qn both approach e^-e-1≈ .692, while both expectations approach the size of a spanning tree, i.e., a random subtree of Kn has approximately n-1 edges.