Connective constant for self-avoiding walks on a skip-chain - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T22:36:42Z http://mathoverflow.net/feeds/question/44506 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44506/connective-constant-for-self-avoiding-walks-on-a-skip-chain Connective constant for self-avoiding walks on a skip-chain Yaroslav Bulatov 2010-11-02T02:04:21Z 2010-11-02T09:36:21Z <p>Suppose we have an undirected graph with integer valued nodes where $0&lt;|i-j|\le 2$ implies nodes $i$ and $j$ are connected. Let $c_n$ be the number of self-avoiding walks on this graph of length $n$ starting at origin. Define the connective constant as</p> <p>$$\mu = \lim_{n\to \infty} c_n^{\frac{1}{n}}$$</p> <p>What is known about $\mu$? This quantity seems to be related to the transition temperature of an Ising model on such graph, has such model been studied?</p> http://mathoverflow.net/questions/44506/connective-constant-for-self-avoiding-walks-on-a-skip-chain/44532#44532 Answer by Yuval Filmus for Connective constant for self-avoiding walks on a skip-chain Yuval Filmus 2010-11-02T09:36:21Z 2010-11-02T09:36:21Z <p>A step is a movement of magnitude 1, a hop of magnitude 2.</p> <p>Denote by $X$ a visited place, by $O$ a place not visited, and by $Y$ the current position. A self-avoiding walk hovers around the states $E_n$, in which the relevant part of the integer line is $X(XO)^nXY$. From this state, the walk can proceed as follows:</p> <ol> <li>Hop left $n$ times and get stuck.</li> <li>Step right to reach $E_0$.</li> <li>Hop right, step left, hop right, reaching $E_0$.</li> <li>Hop $m\geq 1$ times right, then step right, reaching $E_m$.</li> <li>Hop $m\geq 2$ times right, step left, hop $m-1$ times left and get stuck.</li> <li>Hop $m\geq 2$ times right, step left, then hop right, reaching $E_0$.</li> </ol> <p>Options 1,5, where the walk gets stuck, seem not to affect the asymptotics (handwaving). Since option 1 is the only one where $n$ (the subscript of $E_n$) matters, we can disregard the subscripts, and just call it $E$.</p> <p>So we get from $E$ to $E$ by one of the following:</p> <ol> <li>Step right.</li> <li>Hop right, step left, hop right.</li> <li>Hop $m \geq 1$ times right, step right.</li> <li>Hop $m \geq 2$ times right, step left, hop right.</li> </ol> <p>In terms of number of steps, these are $1;3;2,3,4,\ldots;4,5,6,\ldots$. In total, we have "bricks" of sizes $1,2$, and two bricks each of sizes $3,4,\ldots$. The corresponding generating series is</p> <p>$1/(1-x-x^2-2x^3/(1-x)) = (1-x)/(1-2x-x^3)$</p> <p>The denominator has one real root, about 0.453397651516404. So the $k$ term is $O(2.20556943040059^k)$.</p> <p>A walk of length $\ell$ reaches state $E$ after one of $O(\ell^2)$ prefixes, some of which are short. So up to a polynomial, the number of walks is the same as the number of walks starting with $E$. Thus $\mu = 2.20556943040059$.</p>