Mixing
Number of self avoiding paths on a grid graph?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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!
co.combinatorics graph-theory random-walks
asked 4 hours ago
Lorenzo
4851510
add a comment |Â
up vote
1
down vote
favorite
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!
co.combinatorics graph-theory random-walks
asked 4 hours ago
Lorenzo
4851510
math.stackexchange.com/questions/110729/…
– Josiah Park
4 hours ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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!
co.combinatorics graph-theory random-walks
asked 4 hours ago
Lorenzo
4851510
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!
co.combinatorics graph-theory random-walks
co.combinatorics graph-theory random-walks
asked 4 hours ago
Lorenzo
4851510
asked 4 hours ago
Lorenzo
4851510
asked 4 hours ago
Lorenzo
4851510
asked 4 hours ago
Lorenzo
4851510
asked 4 hours ago
Lorenzo
4851510
4851510
math.stackexchange.com/questions/110729/…
– Josiah Park
4 hours ago
add a comment |Â
math.stackexchange.com/questions/110729/…
– Josiah Park
4 hours ago
math.stackexchange.com/questions/110729/…
– Josiah Park
4 hours ago
math.stackexchange.com/questions/110729/…
– Josiah Park
4 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
6
down vote
accepted
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_nsim ccdot N^-2amu^N,
$$
where $a=5/8$ and $mu$ is a lattice-dependent quantity known as the connective constant (it is known to be $sqrt2+sqrt2$ 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,yin 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)|^adelta^2amu^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'_nsim c(theta)^acdot N^-3amu^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/Nto thetain (0,1)$. (If $bequiv N$ or $bequiv 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'_nsim nlogmu.
$$
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.
answered 2 hours ago
Kostya_I
2,5331225
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)$?
– Lorenzo
1 hour ago
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!
– Lorenzo
1 hour ago
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.
– Kostya_I
22 mins ago
add a comment |Â
up vote
2
down vote
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=limlimits_nin mathbbN c_n^frac1n=limlimits_nin 2mathbbN p_n^frac1n$.
According to Madras' paper here an upper bound for $mathbbZ^2$ is given by $p_n leq Cn^−1/2mu^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/2mu^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).
answered 3 hours ago
Josiah Park
1417
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
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_nsim ccdot N^-2amu^N,
$$
where $a=5/8$ and $mu$ is a lattice-dependent quantity known as the connective constant (it is known to be $sqrt2+sqrt2$ 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,yin 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)|^adelta^2amu^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'_nsim c(theta)^acdot N^-3amu^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/Nto thetain (0,1)$. (If $bequiv N$ or $bequiv 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'_nsim nlogmu.
$$
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.
answered 2 hours ago
Kostya_I
2,5331225
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)$?
– Lorenzo
1 hour ago
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!
– Lorenzo
1 hour ago
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.
– Kostya_I
22 mins ago
add a comment |Â
up vote
6
down vote
accepted
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_nsim ccdot N^-2amu^N,
$$
where $a=5/8$ and $mu$ is a lattice-dependent quantity known as the connective constant (it is known to be $sqrt2+sqrt2$ 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,yin 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)|^adelta^2amu^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'_nsim c(theta)^acdot N^-3amu^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/Nto thetain (0,1)$. (If $bequiv N$ or $bequiv 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'_nsim nlogmu.
$$
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.
answered 2 hours ago
Kostya_I
2,5331225
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)$?
– Lorenzo
1 hour ago
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!
– Lorenzo
1 hour ago
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.
– Kostya_I
22 mins ago
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
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_nsim ccdot N^-2amu^N,
$$
where $a=5/8$ and $mu$ is a lattice-dependent quantity known as the connective constant (it is known to be $sqrt2+sqrt2$ 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,yin 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)|^adelta^2amu^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'_nsim c(theta)^acdot N^-3amu^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/Nto thetain (0,1)$. (If $bequiv N$ or $bequiv 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'_nsim nlogmu.
$$
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.
answered 2 hours ago
Kostya_I
2,5331225
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_nsim ccdot N^-2amu^N,
$$
where $a=5/8$ and $mu$ is a lattice-dependent quantity known as the connective constant (it is known to be $sqrt2+sqrt2$ 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,yin 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)|^adelta^2amu^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'_nsim c(theta)^acdot N^-3amu^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/Nto thetain (0,1)$. (If $bequiv N$ or $bequiv 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'_nsim nlogmu.
$$
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.
answered 2 hours ago
Kostya_I
2,5331225
edited 37 mins ago
answered 2 hours ago
Kostya_I
2,5331225
answered 2 hours ago
Kostya_I
2,5331225
answered 2 hours ago
Kostya_I
2,5331225
2,5331225
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)$?
– Lorenzo
1 hour ago
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!
– Lorenzo
1 hour ago
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.
– Kostya_I
22 mins ago
add a comment |Â
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)$?
– Lorenzo
1 hour ago
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!
– Lorenzo
1 hour ago
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.
– Kostya_I
22 mins ago
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)$?
– Lorenzo
1 hour ago
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)$?
– Lorenzo
1 hour ago
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!
– Lorenzo
1 hour ago
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!
– Lorenzo
1 hour ago
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.
– Kostya_I
22 mins ago
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.
– Kostya_I
22 mins ago
add a comment |Â
up vote
2
down vote
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=limlimits_nin mathbbN c_n^frac1n=limlimits_nin 2mathbbN p_n^frac1n$.
According to Madras' paper here an upper bound for $mathbbZ^2$ is given by $p_n leq Cn^−1/2mu^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/2mu^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).
answered 3 hours ago
Josiah Park
1417
add a comment |Â
up vote
2
down vote
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=limlimits_nin mathbbN c_n^frac1n=limlimits_nin 2mathbbN p_n^frac1n$.
According to Madras' paper here an upper bound for $mathbbZ^2$ is given by $p_n leq Cn^−1/2mu^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/2mu^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).
answered 3 hours ago
Josiah Park
1417
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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=limlimits_nin mathbbN c_n^frac1n=limlimits_nin 2mathbbN p_n^frac1n$.
According to Madras' paper here an upper bound for $mathbbZ^2$ is given by $p_n leq Cn^−1/2mu^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/2mu^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).
answered 3 hours ago
Josiah Park
1417
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=limlimits_nin mathbbN c_n^frac1n=limlimits_nin 2mathbbN p_n^frac1n$.
According to Madras' paper here an upper bound for $mathbbZ^2$ is given by $p_n leq Cn^−1/2mu^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/2mu^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).
answered 3 hours ago
Josiah Park
1417
edited 1 hour ago
answered 3 hours ago
Josiah Park
1417
answered 3 hours ago
Josiah Park
1417
answered 3 hours ago
Josiah Park
1417
1417
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f312993%2fnumber-of-self-avoiding-paths-on-a-grid-graph%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
math.stackexchange.com/questions/110729/…
– Josiah Park
4 hours ago