The Taub Faculty of Computer Science Events and Talks

A d-dimensional polycube is a facet-connected set of cells (cubes) on the d-dimensional cubical lattice. Let Ad(n) denote the number of d-dimensional polycubes (distinct up to translations) with n cubes, and λd denote the limit of the ratio Ad(n+1)/Ad(n) as n approaches infinity. The exact value of λd is still unknown rigorously for d ≥ 2; the asymptotics of λd, as d approaches infinity, also remained elusive as of today.

In this talk, I will show how we revisit and extend the approach presented by Klarner and Rivest in 1973 to bound A2(n) (the number of polyominoes with n squares) from above. Our contributions are:
• Using available computing power, we prove that λ2 ≤ 4.5252. This is the first improvement of the upper bound on λ2 in almost half a century;
• We prove that λd ≤ (2d−2)e+o(1) for any value of d ≥ 2, using a novel construction of a rational generating function which dominates that of the sequence (Ad(n));
• For the case of d = 3, this provides a subtantial improvement of the upper bound on λ3 from 12.2071 to 9.8073;
• We implement an iterative process in three dimensions, which improves further the upper bound on λ3 to 9.3835;

This work was done jointly with Gill Barequet (Technion, Haifa).