Uniform and balanced sampling of connected planar graph partitions is hard unless RP=NP, the flip walk mixes exponentially slowly on explicit triangulation families, and tractable cases include series-parallel and bounded-treewidth graphs.
On the scaling limit of planar self-avoiding walk
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
A planar self-avoiding walk (SAW) is a nearest neighbor random walk path in the square lattice with no self-intersection. A planar self-avoiding polygon (SAP) is a loop with no self-intersection. In this paper we present conjectures for the scaling limit of the uniform measures on these objects. The conjectures are based on recent results on the stochastic Loewner evolution and non-disconnecting Brownian motions. New heuristic derivations are given for the critical exponents for SAWs and SAPs.
fields
cs.CC 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Complexity and Geometry of Sampling Connected Graph Partitions
Uniform and balanced sampling of connected planar graph partitions is hard unless RP=NP, the flip walk mixes exponentially slowly on explicit triangulation families, and tractable cases include series-parallel and bounded-treewidth graphs.