wiki:public/20131015

Project: Counting Polyominoes in the Limit

Team: Prof. Dr. Günter Rote, Prof. Dr. Gill Barequet, Mira Shalah

Research institution: Freie Universität Berlin and the Technion, Haifa

Abstract: A polyomino (or "animal") is an edge-connected set of squares on the two-dimensional square lattice. The research of polyominoes is motivated by problems arising in statistical physics, e.g., computing the mean cluster density in percolation processes. We investigate one of the fundamental problems related to polyominoes, namely, computing their asymptotic growth rate, that is, the ratio between the number of polyominoes of size n+1 and of size n, as n→∞. This limit is known as Klarner’s constant, λ. Determining the exact value of λ (or even good bounds) is an extremely hard problem in enumerative combinatorics.

For attacking this problem, we count polyominoes on a "twisted cylinder". This is a wrap-around spiral-like structure which can be built by adding one square at a time in a uniform way; therefore the incremental buildup of polyominoes can be modeled very conveniently. This is visualized in a recent video by Gill Barequet and Mira Shalah, see http://www.computational-geometry.org/SoCG-videos/socg13video/

The number of polyominoes on the twisted cylinder is a lower bound on the number of polyominoes in the plane, in which we are actually interested. The larger the width W of the cylinder, the better the bound, but the more computation is needed. In 2004, we had developed a serial computer program which required extremely high computing resources by the standards of that time, both in terms of running time and main memory, going up to width W=22. Before the start of this project, the bounds on the growth constant λ (Klarner's constant) were 3.985 from below and 4.6 from above. The bound 3.985 comes from the twisted cylinder of width W=23. We set out to push the lower bound above 4.

On May 20, we succeeded to run the iteration for W=27, using about 36 hours of runtime in total, distributed over several runs and writing intermediate results to disk. The lower bound on λ broke through the mythical barrier of 4.0 on May 19 at 8:26 p.m. after 120 iterations. The lower bound converged to 4.00254 after 290 iterations, establishing the current record. The proof of this bound consists essentially of an array of floating-point numbers, which is about 450 GBytes long. We are currently working on an independent program for checking this "proof", as well as further measures that would make it possible to run W=28.

Last modified 6 years ago Last modified on Aug 2, 2013 9:47:57 AM

Attachments (2)

Download all attachments as: .zip