Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling

DOI10.4169/amer.math.monthly.124.7.637zbMath1391.60175OpenAlexW2736833145MaRDI QIDQ4575405

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) 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)

Related Items

Mixing times for the simple exclusion process in ballistic random environment, The-square-and-add Markov chain, Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations, Involutive random walks on total orders and the anti-diagonal eigenvalue property, Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines, Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields, On reachable assignments under dichotomous preferences, Unnamed Item, Biased opinion dynamics: when the devil is in the details, Internal DLA on cylinder graphs: fluctuations and mixing, What matters in school choice tie-breaking? How competition guides design, Sequential Importance Sampling for Estimating the Number of Perfect Matchings in Bipartite Graphs: An Ongoing Conversation with Laci, Unnamed Item, Random walk on the symplectic forms over a finite field, Sherali-adams strikes back, Reconfiguration of connected graph partitions via recombination, The continuum directed polymer in Lévy noise, Attracting random walks, Unnamed Item, Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph homomorphisms between trees
• Number of walks and degree powers in a graph
• Proof of London's conjecture on sums of elements of positive matrices
• Markov chains indexed by trees
• A partially ordered set of functionals corresponding to graphs
• The sample size required in importance sampling
• A correlation inequality for bipartite graphs
• Two inequalities in nonnegative symmetric matrices
• Mathematics and Computer Science: Coping with Finiteness
• On the Importance Sampling of Self-Avoiding Walks
• Three observations on nonnegative matrices