Self-testing algorithms for self-avoiding walks

DOI10.1063/1.533197zbMath0977.82020OpenAlexW2051818974MaRDI QIDQ2737885

Alistair Sinclair, Dana Randall

Publication date: 30 August 2001

Published in: Journal of Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1063/1.533197

zbMATH Keywords

Markov chain Monte Carlo algorithm

Mathematics Subject Classification ID

Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Markov processes (60J99)

Related Items

Persistence length convergence and universality for the self-avoiding random walk ⋮ Invasion percolation on Galton-Watson trees ⋮ On Sampling Simple Paths in Planar Graphs According to Their Lengths ⋮ The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time

Cites Work

• Geometric bounds for eigenvalues of Markov chains
• Random generation of combinatorial structures from a uniform distribution
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Exponential convergence to equilibrium for a class of random-walk models
• Self-avoiding walk in five or more dimensions. I: The critical behaviour
• New lower bounds on the self-avoiding-walk connective constant
• Monotonicity of the number of self-avoiding walks
• Approximating the Permanent
• Monte-Carlo approximation algorithms for enumeration problems
• THE LACE EXPANSION FOR SELF-AVOIDING WALK IN FIVE OR MORE DIMENSIONS
• Upper Bounds for the Connective Constant of Self-Avoiding Walks
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Lower bound on the connective constant for square lattice self-avoiding walks
• Self-avoiding polygons on the square lattice
• FURTHER RESULTS ON THE RATE OF CONVERGENCE TO THE CONNECTIVE CONSTANT OF THE HYPERCUBICAL LATTICE