Formulae and Growth Rates of High-Dimensional Polycubes

September 17, 2009
2:50 pm - 4:00 pm
Halligan 111
Speaker: Gill Barequet, Tufts University
Host: Sam Guyer

Abstract

A d-dimensional polycube of size n is a (d-1)-face-connected set of n cubes in d dimensions. Fixed polycubes are considered distinct if they differ in their shape or orientation. A properd-dimensional polycube cannot be embedded in d-1 dimensions. In this talk I will show closed formulae for fixed (proper and improper) polycubes, and show that the growth-rate limit of the number of polycubes in d dimensions is similar to 2ed-o(d) (conjectured to be (2d-3)e+O(1/d)) as d tends to infinity.

Joint work with Ronnie Barequet (Math and Computer Science, TAU) and Guenter Rote (Computer Science, FU).

(Gill is currently a visiting professor here at Tufts)