Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling

DOI10.4169/AMER.MATH.MONTHLY.124.7.637MaRDI QIDQ4575405zbMATH OpenOpenAlexFDO

Authors David A. Levin, Yuval Peres

Publication date 13 July 2018

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4169/amer.math.monthly.124.7.637

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Recommendations

• scientific article; zbMATH DE number 2151249
• Graph homomorphisms through random walks
• Random walks on graphs and Monte Carlo methods
• Random walks on graphs: ideas, techniques and results
• The Markov chain asymptotics of random mapping graphs
• On the Structure and Computation of Random Walk Times in Finite Graphs
• Counting and exploring sizes of Markov equivalence classes of directed acyclic graphs
• On distributions computable by random walks on graphs
• On Distributions Computable by Random Walks on Graphs
• scientific article; zbMATH DE number 878897

Cites work

• A correlation inequality for bipartite graphs
• A partially ordered set of functionals corresponding to graphs
• Graph homomorphisms between trees
• scientific article; zbMATH DE number 6789278 (Why is no real title available?)
• Large networks and graph limits
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Markov chains indexed by trees
• Mathematics and computer science: coping with finiteness
• Number of walks and degree powers in a graph
• On the importance sampling of self-avoiding walks
• Proof of London's conjecture on sums of elements of positive matrices
• The sample size required in importance sampling
• Three observations on nonnegative matrices
• Two inequalities in nonnegative symmetric matrices

Cited in

(24)

• Random walk on the symplectic forms over a finite field
• The continuum directed polymer in Lévy noise
• Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
• The-square-and-add Markov chain
• Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines
• Internal DLA on cylinder graphs: fluctuations and mixing
• What matters in school choice tie-breaking? How competition guides design
• Mixing times for the simple exclusion process in ballistic random environment
• Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations
• Involutive random walks on total orders and the anti-diagonal eigenvalue property
• Sequential importance sampling for estimating the number of perfect matchings in bipartite graphs: an ongoing conversation with Laci
• scientific article; zbMATH DE number 7370527 (Why is no real title available?)
• scientific article; zbMATH DE number 7625198 (Why is no real title available?)
• Sherali-adams strikes back
• Sherali-Adams strikes back
• Reconfiguration of connected graph partitions via recombination
• Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
• On reachable assignments under dichotomous preferences
• Biased opinion dynamics: when the devil is in the details
• Hardness self-amplification: simplified, optimized, and unified
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Learning algorithms for verification of Markov decision processes
• A very short proof of Sidorenko's inequality for counts of homomorphisms between graphs
• Attracting random walks

This page was built for publication: Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling

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