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

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 460, 740, 1192, 1918, 3064, 4910, 7872, 12620, 20114, 32150, 51396, 82160, 130730, 208506, 332616, 530588, 843222, 1342662, 2138280, 3405346, 5406522, 8597632, 13674278, 21748530, 34501460, 54807754, 87077354

Offset: 0

Author

David Galvin, Jul 28 2023

Keywords

• nonn
• walk

Comments

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).

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.

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.

Examples

			With the x-axis and the y-axis both oriented positively, here are the 6 walks of length 3:
 * (0,0)-(1,0)-(2,0)-(3,0)
 * (0,0)-(1,0)-(2,0)-(2,1)
 * (0,0)-(1,0)-(1,-1)-(1,-2)
 * (0,0)-(0,1)-(0,2)-(0,3)
 * (0,0)-(0,1)-(0,2)-(1,2)
 * (0,0)-(0,1)-(-1,1)-(-2,1)
The following is not a valid walk, because it takes two consecutive turns:
 * (0,0)-(1,0)-(1,-1)-(0,-1)
		

References

• 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.

Links

• A. Blanca, Y. Chen, D. Galvin, D. Randall and P. Tetali, Phase Coexistence for the Hard-Core Model on Z^2, arXiv:1611.01115 [math.PR], 2016-2018.
• Haoquan Liang, Phase Coexistence for the Hard-Core Model on Z^2: Improved Bounds, Penn State Honors Thesis, Spring 2021.

Crossrefs

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

Formula

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.

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.