6
$\begingroup$

Let $G$ be an $n \times n$ grid graph. Is there anything known about the asymptotic growth rate of the number of self avoiding paths from $(0,0)$ to $(n,b)$ (from the lower left corner to some arbitrary point on the right hand side)?

For example, is there anything known about the $b$ that maximizes this number? A limiting probability distribution on $[0,1]$ for the value of $b$ (if we pick a self avoiding walk from $(0,0)$ to $x = n$ uniformly at random)?

Some similar questions go unanswered:

Any approximation algorithms for self-avoiding walks?

How does the number of self-avoiding paths between two points scale, in a square/cubic lattice?

Thank you!

$\endgroup$
1

3 Answers 3

10
$\begingroup$

UPD: the answer below is in fact completely wrong - it deals with counting walks $\gamma$ weighted by $\mu^{-\text{length}(\gamma)}$. It is clear that without restricting or penalizing for the lengths of the walks, the number of walks will grow exponentially with the volume (i. e., as $\eta^{N^2}$ for some $\eta>1$). In fact, in this paper it is shown that a walk chosen uniformly from this measure (or even from a measure $\hat{\mu}^{-\text{length}(\gamma)}$ with any $\hat{\mu}<\mu$) is space-filling in the scaling limit. It is also conjectured that its scaling limit is SLE$_8$, which suggests that it is in the same universality class as the perimeter of the Uniform Spanning tree. If we buy that, then the number of walks should behave similarly to the number of spanning trees (although with a different $\eta$), which is given by the determinant of the graph Laplacian. The asymptotics of the latter in rectilinear domains was studied, although with different boundary conditions (Kenyon has Dirichlet boundary conditions and we would be interested in Dirichlet+Neumann ones). As far as the dependence on $b$ is concerned, (i. e., if we are only interested in the ratios $P'_n(b_1)/P'_n(b_2)$ with $b_{1,2}$ in the bulk of the right side of the square), it should be captured by the $SLE_8$ partition function, and then the same conclusion as in discussion below might hold with a different exponent (namely, $a=\frac{6-\kappa}{2\kappa}$, which for $\kappa=8$ equals $-\frac18$). But again, these conjectures are all quite far-fetched.

Old Answer

Lawler, Schramm and Werner conjectured that the number $R_n$ of self-avoiding walks in the rectangle $[-N;N]\times[0;N]$ connecting the origin to the point $(0;N)$ behaves like $$ R_n\sim c\cdot N^{-2a}\mu^N, $$ where $a=5/8$ and $\mu$ is a lattice-dependent quantity known as the connective constant (it is known to be $\sqrt{2+\sqrt{2}}$ for hexagonal lattice and only numerically known for other lattices). Moreover, they conjectured that the measure should have a conformally covariant scaling limit, meaning that if $\Omega$ is another simply-connected domain and $x,y\in \partial \Omega$, with the boundary being nice (say, horizontal or vertical straight lines) near $x,y$, then the number of SAW from $a$ to $b$ in a $\delta$-mesh lattice approximation to $\Omega$ should behave like $$ R^\Omega_n \sim c |\varphi'(x)|^{a}|\varphi'(y)|^{a}\delta^{2a}\mu^{\delta^{-1}}, $$ where $\varphi$ is a conformal map from $\Omega$ to the rectangle $(-1,1)\times(0,1)$ that maps $x$ to the origin and $y$ to $i$. (We can also fix $|\varphi'(x)|=1$, and then $|\varphi'(y)|$ is proportional to the normal derivative of the Poisson kernel with a pole at $x$.) A straightforward extension of their conjecture would be that the number of SAW from the origin to $(N,b)$, with a given $b$, behaves like $$ P'_n\sim c(\theta)^a\cdot N^{-3a}\mu^N, $$ where $c(\theta)$ is proportional to the normal derivative at $(1;\theta)$ of the Poisson kernel in $(0;1)^2$ with a "pole" at the origin, and we are in the regime $b/N\to \theta\in (0,1)$. (If $b\equiv N$ or $b\equiv 0$, the power law exponent should change to $-4a$.)

No-one doubts the conformal covariance ansatz of Lawler, Schramm and Werner; but it is wide open to prove it rigorously. The best you can do rigorously is, probably, $$ \log P'_n\sim n\log\mu. $$ I am not sure this is explicitly done anywhere, but the general idea is that all 'reasonable' models of planar SAW should obey this property with the same $\mu$; for instance, here it is done for arbitrary paths, bridges, and closed paths.

$\endgroup$
8
  • $\begingroup$ Great answer, thanks! Do you think you could say a little more explicitly what $c(b)$ is? Which Poisson kernel? I'm also a little confused by the notation: $P_n'(b)$ refers to the number of SAW from $(0,0)$ to $(n,b)$? $\endgroup$
    – Elle Najt
    Oct 16, 2018 at 21:03
  • $\begingroup$ So the conjecture is that probability distribution is going to be proportional to $c(\theta)^a$ (in the regime $\theta \in (0,1)$)? It would be helpful for me if you could write the conjectured probability distribution a little more explicitly, since I'm not too familiar with this stuff. I will try to read the papers you suggest, thank you! $\endgroup$
    – Elle Najt
    Oct 16, 2018 at 21:11
  • $\begingroup$ yes, the notation was perhaps unclear, I edited the text. The Poisson kernel refers to the unique non-negative harmonic function in the domain that extends continuously to all points of the boundary except for $x$; the normalization may be whatever it is - the asymptotics includes some unknown, lattice-dependent multiplicative constant anyways. For the square, I guess, you can write the Poisson kernel explicitly using elliptic functions. $\endgroup$
    – Kostya_I
    Oct 16, 2018 at 22:32
  • $\begingroup$ Are there any families of graphs or lattices where an exact count of the number of self avoiding walks between points is known? $\endgroup$
    – Elle Najt
    Oct 17, 2018 at 16:37
  • $\begingroup$ I'm a little confused here. It seems like the mass assigned to SAW in the LSW paper decays with the length of the walk. So I'm not sure how (maybe I'm misunderstanding) 3.3.1 in that paper can be used to count the number of self avoiding walks. Could you expand on this? $\endgroup$
    – Elle Najt
    Nov 30, 2018 at 23:19
3
$\begingroup$

The problem you are interested in is related to enumerating self-avoiding walks in a graph (one can consider self-avoiding polygons, which are closed SAWs, also) and is a difficult problem computationally.

For an infinite graph, the asymptotic behavior of the number of length $n$ self-avoiding walks (or self-avoiding polygons) is denoted $c_{n}$ ($p_{n}$ resp.) and depends on the structure of one's graph namely on the connective constant $\mu=\lim\limits_{n\in \mathbb{N}} c_{n}^{\frac{1}{n}}=\lim\limits_{n\in 2\mathbb{N}} p_{n}^{\frac{1}{n}}$. According to Madras' paper here an upper bound for $\mathbb{Z}^2$ is given by $p_n \leq Cn^{−1/2}\mu^n$ with a better estimate anticipated (see @Kostya_I's answer).

Edit: @Kostya_I's comments on conformal mappings supercedes most of the information here. The best estimate that was found after looking through a few papers improves Madras' $p_n \leq Cn^{−1/2}\mu^n$ mentioned above to $p_n ≤ n^{−3/2+o(1)}\mu^{n}$ by A. Hammond here (for a set of even $n$ of full density).

$\endgroup$
1
$\begingroup$

The usual methods fail when dealing with self avoiding walks. One approach I have pondered is to treat the walk as a parametric function of sorts in which the integral approximates the length of the walk and it's constrained by a integer value distances about $n$ number of $x$ & $y$ intercepts in such a way as it does not intersect with itself. So for a $n$ by $n$ lattice in which the walk starts at $0,0$, the functional would be of the form $f(x,y)=a_0y^n+a_1y^{n-1}...b_0x^n...$ .

The graph would be inverted subject to the relevant constraints to find some sort of asymptotic behavior.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.