Formulae for Polyominoes on Twisted Cylinders
Staff - Faculty of Informatics
Start date: 10 December 2012
End date: 11 December 2012
The Faculty of Informatics is pleased to announce a seminar given by Gill Barequet
DATE: Monday, December 10th, 2012
PLACE: USI Università della Svizzera italiana, room A23, Red building (Via G. Buffi 13)
TIME: 15.30
ABSTRACT:
Polyominoes are edge-connected sets of cells on the square lattice $\mathbb{Z}^2$, or, in general, on any lattice. For example, Tetris pieces are polyominoes on the square lattice. Surprisingly, polyominoes in higher dimensions are a central research area in statistical mechanics.
We investigate polyominoes on square lattices embedded on so-called \emph{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 cylinders with perimeters up to 10. The recurrence for $p=10$ includes 2168 terms, with the largest coefficient being about $6.39 \cdot 10^{129}$ (432 bits).
Joint work with Gadi Aleksandrowicz (CS, Technion, Haifa), Andrei Asinowski (Math, Technion), and Ronnie Barequet (CS, Tel Aviv University).
BIO:
Gill Barequet is an Associate Professor of Computer Science at the Technion (Israel Institute of Technology), Haifa. He earned his Ph.D. in computer science in 1994 from Tel Aviv University. His research interests include computational and discrete geometry, combinatorics, and combinatorial geometry.
HOST: Prof. Evanthia Papadopoulou
