Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
DOI10.4169/AMER.MATH.MONTHLY.124.7.637zbMATH Open1391.60175OpenAlexW2736833145MaRDI QIDQ4575405FDOQ4575405
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
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
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)
Cites Work
- The sample size required in importance sampling
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Large networks and graph limits
- Proof of London's conjecture on sums of elements of positive matrices
- A partially ordered set of functionals corresponding to graphs
- Two inequalities in nonnegative symmetric matrices
- Mathematics and computer science: coping with finiteness
- Graph homomorphisms between trees
- Three observations on nonnegative matrices
- Markov chains indexed by trees
- Number of walks and degree powers in a graph
- A correlation inequality for bipartite graphs
- On the importance sampling of self-avoiding walks
- Title not available (Why is that?)
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
- Title not available (Why is that?)
- On reachable assignments under dichotomous preferences
- Title not available (Why is that?)
- 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
- Hardness self-amplification: simplified, optimized, and unified
- Biased opinion dynamics: when the devil is in the details
- Attracting random walks
- Reconfiguration of connected graph partitions via recombination
- Title not available (Why is that?)
- The continuum directed polymer in Lévy noise
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)
