Formulae for Polyominoes on Twisted Cylinders

September 6, 2012
2:50 pm - 4:00 pm
Halligan 111

Abstract

Polyominoes are edge-connected sets of cells on the square lattice Z^2, or, in general, on any lattice. Tetris pieces are examples of polyominoes on the square lattice. Surprisingly, polyominoes in higher dimensions is a central research area in statistical mechanics. We investigate polyominoes on square lattices embedded on so-called "twisted cylinders". Such lattices are interesting, for example, because they were used for setting the currently best-known lower bound (3.9801...) on the asymptotic growth rate of polyominoes in the plane.

In this work we show further that the growth-rate limit of polyominoes on twisted cylinders approaches that of polyominoes in the plane, as the perimeter of the cylinder tends to infinity.

We also prove that for any fixed value of p, the formula enumerating polyominoes on a twisted cylinder of perimeter p satisfies a linear recurrence whose complexity grows exponentially with p. The constructive proof is based on a transfer-matrix method. Recovering the formulas is challenging since the recurrences are very complex and they have extremely large coefficients even for small values of p. By using the Berlekamp-Massey algorithm we were able to recover the formulas for up to p=10. The recurrence for p=10 includes 2168 terms, with the largest coefficient being about 6.39 x 10^{129} (432 bits).

Joint work with Gadi Aleksandrowicz (CS, Technion, Haifa), Andrei Asinowski (Math, Technion), and Ronnie Barequet (CS, Tel Aviv University).

Gill Barequet is an associate professor of computer science at the Techion---Israel Institute of Technology. He received his Ph.D. in Computer Science from Tel Aviv University in 1994, and worked as a postdoctoral fellow at the department of computer science of Johns Hopkins University. His research interests include computational and combinatorial geometry.