Chainsawing Cayley Trees: Markovian Methods in Tree Enumeration
DOI:
https://doi.org/10.69760/lumin.2025000204Keywords:
Cayley’s formula, labeled trees, Markov chain, random pruning, spanning trees, network reliability, forest enumerationAbstract
We revisit Cayley’s classical result that there are nn−2 labeled trees on nn vertices (Cayley’s formula). We introduce a stochastic pruning process on this space of Cayley trees, which we term a Markov chainsaw. In this model, edges of a labeled tree are cut or reattached randomly over time, yielding a Markov chain on the space of forests. We derive rigorous results for this process: we prove it is irreducible and aperiodic on the forest state space, and we find its stationary distribution via detailed balance. In particular, the uniform spanning-tree case recovers Cayley’s count and relates to loop-erased random walks and Wilson’s algorithm. We also implement computational experiments (in Python/NetworkX) for small nn to illustrate convergence and mixing; empirical frequencies agree with our theoretical stationary laws. Our contributions tie together classical enumeration (e.g. Prüfer codes), Markov‐chain theory (coupling and convergence), and applications in random graph processes and network reliability.
References
Addario-Berry, L., Broutin, N., & Holmgren, C. (2014). Cutting down trees with a Markov chainsaw. Annals of Applied Probability, 24(6), 2297–2339.
Aldous, D. (1990). The random walk construction of uniform spanning trees and uniform labelled trees. SIAM Journal on Discrete Mathematics, 3(4), 450–465.
Ball, M. O. (1986). Complexity of network reliability computation. Networks, 10(2), 153–165.
Berzunza Ojeda, G., & Holmgren, C. (2022). Invariance principle for fragmentation processes derived from conditioned stable Galton–Watson trees. Electronic Journal of Probability, 27, 1–30.
Broder, A. Z. (1989). Generating random spanning trees. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (pp. 442–447).
Colbourn, C. J. (1987). The Combinatorics of Network Reliability. New York: Oxford University Press.
Diaconis, P. (1988). Group Representations in Probability and Statistics. Institute of Mathematical Statistics.
Evans, S., Pitman, J., & Winter, A. (2006). Rayleigh processes, real trees, and root growth with re-grafting. Probability Theory and Related Fields, 134(1), 81–126.
Flajolet, P., & Sedgewick, R. (2009). Analytic Combinatorics. Cambridge, UK: Cambridge University Press.
Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008). Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference (pp. 11–15).
Jerrum, M., & Sinclair, A. (1989). Approximating the permanent. SIAM Journal on Computing, 18(6), 1149–1178.
Kuba, M., & Panholzer, A. (2006). Isolation of a single node in random recursive trees. Journal of Graph Theory, 53(1), 1–27.
Levin, D. A., Peres, Y., & Wilmer, E. L. (2009). Markov Chains and Mixing Times. Providence, RI: American Mathematical Society.
Moon, J. W. (1970). Counting Labelled Trees. Toronto: Canadian Mathematical Congress.
Pemantle, R. (1991). Choosing a spanning tree for the integer lattice uniformly. Annals of Probability, 19(4), 1559–1574.
Pitman, J. (1999). Coalescent random forests. Journal of Combinatorial Theory, Series A, 85(2), 165–193.
Prüfer, H. (1918). Neuer Beweis eines Cayley’schen Satzes über die Anzahl der Bäume. Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin, 1918, 103–110.
Stanley, R. P. (2012). Enumerative Combinatorics, Volume 2 (2nd ed.). Cambridge, UK: Cambridge University Press.
West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Upper Saddle River, NJ: Prentice Hall.
Wilson, D. B. (1996). Generating random spanning trees more quickly than the cover time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (pp. 296–303).
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Luminis Applied Science and Engineering
This work is licensed under a Creative Commons Attribution 4.0 International License.
