Gill Barequet:
 Formulae for Polyominoes on Twisted Cylinders
<br><br>
Polyominoes are edge-connected sets of cells on the orthogonal lattice
$\mathbb{Z}^2$, or, in general, on any lattice.
We investigate polyominoes on a rectangular lattice 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 complex and 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 \cdot 10^{129}$ (432 bits).
<br><br>
If time allows, I will briefly present a related result, namely, an
alternative method for computing the recurrence for $p=3$, which uses
permutations with forbidden patterns, and elaborate more on how the lower
bound 3.98 on the growth rate of polyominoes in the plane was set.

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