Counting trees with random walks

DOI10.1016/J.EXMATH.2018.07.001MaRDI QIDQ2003395zbMATH OpenOpenAlexWikidataFDO

Authors Giulio Iacobelli, Daniel R. Figueiredo, 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

Markov chain tree theoremmatrix-tree theoremrandom walksspanning trees

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Random walks on graphs (05C81) Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Recommendations

• An elementary proof of a matrix tree theorem for directed graphs
• Linear algebraic techniques for spanning tree enumeration
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Counting spanning trees in grid graphs
• Matrix-tree theorem of digraphs via signless Laplacians

Cites work

• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• A proof of the Markov chain tree theorem
• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• scientific article; zbMATH DE number 782053 (Why is no real title available?)
• scientific article; zbMATH DE number 6665536 (Why is no real title available?)
• scientific article; zbMATH DE number 3047763 (Why is no real title available?)
• Line-digraphs, arborescences and theorems of Tutte and Knuth
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• Markov paths, loops and fields. École d'Été de Probabilités de Saint-Flour XXXVIII -- 2008
• Probability on trees and networks
• Random Perturbations of Dynamical Systems
• Random walk: A modern introduction
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees

Cited in

(5)

• Inferring a tree from walks
• A proof of the Markov chain tree theorem
• Stochastic enumeration method for counting trees
• Matrices with zero row sums, tree theorems and a Markov chain on trees
• Three conjectures of Ostrander on digraph Laplacian eigenvectors

This page was built for publication: Counting trees with random walks

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