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

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

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

• scientific article; zbMATH DE number 6789278 (Why is no real title available?)
• A correlation inequality for bipartite graphs
• A partially ordered set of functionals corresponding to graphs
• Graph homomorphisms between trees
• 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

(22)

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

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)