A364580 - OEIS

%I #27 Sep 03 2023 00:03:21

%S 1,2,4,6,10,16,26,42,68,110,178,288,460,740,1192,1918,3064,4910,7872,

%T 12620,20114,32150,51396,82160,130730,208506,332616,530588,843222,

%U 1342662,2138280,3405346,5406522,8597632,13674278,21748530,34501460,54807754,87077354

%N Number of n-step self-avoiding walks on the square Manhattan lattice that do not take two consecutive turns.

%C The square Manhattan lattice is an oriented square lattice in which the orientations are constant along horizontal and vertical lines, with pairs of consecutive lines having alternating orientations (similar to a generic portion of the streets and avenues of midtown Manhattan).

%C In the hard-core (independent set) model on the ordinary two-dimensional integer lattice, the contours separating odd-occupied regions from even-occupied regions can be viewed as self-avoiding walks on the square Manhattan lattice that do take two consecutive turns. It follows via a standard Peierls argument that if a(n) grows like mu^n then the hard-core model on the ordinary two-dimensional integer lattice exhibits phase coexistence for all values of the fugacity above mu^4-1. See the Blanca, Chen, Galvin, Randall and Tetali reference for details.

%C In the Blanca et al. reference these are called "taxi walks" because a savvy passenger in a Manhattan cab would be suspicious if the cab took two consecutive turns.

%D A. Blanca, Y. Chen, D. Galvin, D. Randall and P. Tetali, Phase Coexistence for the Hard-Core Model on Z^2, Combinatorics, Probability and Computing, 28 (2019), 1-22.

%H A. Blanca, Y. Chen, D. Galvin, D. Randall and P. Tetali, <a href="https://arxiv.org/abs/1611.01115">Phase Coexistence for the Hard-Core Model on Z^2</a>, arXiv:1611.01115 [math.PR], 2016-2018.

%H Haoquan Liang, <a href="https://honors.libraries.psu.edu/files/final_submissions/7654">Phase Coexistence for the Hard-Core Model on Z^2: Improved Bounds</a>,  Penn State Honors Thesis, Spring 2021.

%F a(n) = f(n)*mu^n where mu is a constant and f(n) is subexponential in n. This follows from the subadditivity of log a(n). See the Blanca, Chen, Galvin, Randall and Tetali reference for details.

%F mu is known to lie between 1.5186 and 1.5874. See the Blanca et al. reference for the lower bound, and the Liang link for the upper bound.

%e With the x-axis and the y-axis both oriented positively, here are the 6 walks of length 3:

%e  * (0,0)-(1,0)-(2,0)-(3,0)

%e  * (0,0)-(1,0)-(2,0)-(2,1)

%e  * (0,0)-(1,0)-(1,-1)-(1,-2)

%e  * (0,0)-(0,1)-(0,2)-(0,3)

%e  * (0,0)-(0,1)-(0,2)-(1,2)

%e  * (0,0)-(0,1)-(-1,1)-(-2,1)

%e The following is not a valid walk, because it takes two consecutive turns:

%e  * (0,0)-(1,0)-(1,-1)-(0,-1)

%Y A117633 gives the number of self-avoiding walks on the square Manhattan lattice without the restriction on consecutive turns.

%K nonn,walk

%O 0,2

%A _David Galvin_, Jul 28 2023