Self Avoiding Walk Enumerations - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T01:39:42Z http://mathoverflow.net/feeds/question/52813 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52813/self-avoiding-walk-enumerations Self Avoiding Walk Enumerations Alex R. 2011-01-22T03:57:57Z 2011-01-23T04:48:16Z <p>Let \$c(n)\$ be the number of Self avoiding walks (SAW) of length \$n\$ on an infinite lattice \$L\$. Are there any known non-geometric interpretations of \$c(n)\$?. For example, is there a number theoretic version of SAW's? We know for example that Catalan numbers count a myriad of things so perhaps SAW appear elsewhere? For reference, \$c(n)\$ for the usual 2-D integer lattice looks like 1,4,12,36,100,284,780,,... for \$n=0,1,2,...</p> <p>The online integer sequence library gives no results other than the number of SAWs.</p> <p>Note: I'm not exactly interested in characterizations, such as the ones in <a href="http://mathoverflow.net/questions/41543/how-to-characterize-a-self-avoiding-path" rel="nofollow">this</a> question. Something like the <a href="http://books.google.com/books?id=rlrnzwgujZUC&amp;pg=PA57&amp;dq=hammersley+welsch+self+avoiding+walk&amp;hl=en&amp;ei=91E6Tc3vIIjQsAOJx4WDAw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCgQ6AEwAA#v=onepage&amp;q&amp;f=false" rel="nofollow">Hammersley and Welsh</a> characterization in terms of excursion width is closer to what I'm looking for. In fact one sees partition functions crop up naturally, with theorems of Hardy and Ramanujan used for growth estimates. </p> http://mathoverflow.net/questions/52813/self-avoiding-walk-enumerations/52911#52911 Answer by Nathan Clisby for Self Avoiding Walk Enumerations Nathan Clisby 2011-01-23T04:48:16Z 2011-01-23T04:48:16Z <p>I strongly doubt that there exists a non-trivial bijection between self-avoiding walks on Z^d and other combinatorial objects. I don't have any intuition as to whether the generating function may have some other number theoretic interpretation, but I haven't seen or heard anything in this regard.</p> <p>SAWs are sufficiently complicated that it seems almost certain that the generating function for SAWs even on the square lattice them is non-holonomic (see e.g. Andrew Rechnitzer discussing the related model of self-avoiding polygons, "Haruspicy 2: The anisotropic generating function of self-avoiding polygons is not D-finite", <a href="http://www.math.ubc.ca/~andrewr/pub_list.html" rel="nofollow">link</a>), and the model is unlikely to be "solvable" in the conventional sense.</p> <p>FYI, Iwan Jensen has enumerated SAWs on Z^2 to 71 steps <a href="http://www.ms.unimelb.edu.au/~iwan/saw/SAW_ser.html" rel="nofollow">here</a>, and higher dimensional enumerations due to Gordon Slade, Richard Liang and I are available <a href="http://www.math.ubc.ca/~slade/lacecounts/index.html" rel="nofollow">here</a>.</p>