Counting trees with random walks

DOI10.1016/j.exmath.2018.07.001zbMath1415.05079MaRDI QIDQ2003395

Daniel R. Figueiredo, Giulio Iacobelli, Valmir C. Barbosa

Publication date: 8 July 2019

Published in: Expositiones Mathematicae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.exmath.2018.07.001

zbMATH Keywords

random walks; Markov chain tree theorem; matrix-tree theorem; spanning trees

Mathematics Subject Classification ID

05C05: Trees

60G50: Sums of independent random variables; random walks

05C30: Enumeration in graph theory

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

05C20: Directed graphs (digraphs), tournaments

05C81: Random walks on graphs

Related Items

Three conjectures of Ostrander on digraph Laplacian eigenvectors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Markov paths, loops and fields. École d'Été de Probabilités de Saint-Flour XXXVIII -- 2008
• Line-digraphs, arborescences and theorems of Tutte and Knuth
• A proof of the Markov chain tree theorem
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• Probability on Trees and Networks
• Random Perturbations of Dynamical Systems
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Random Walk: A Modern Introduction
• A Combinatorial Proof of the All Minors Matrix Tree Theorem