Department of Computer Science DIKU > Research > Algorithms and Programming Languages Section (APL) > EADS > Upcoming talks and events > EADS Talk by: Mira Shalah
EADS Talk by: Mira Shalah
A Method for Generating Formulae for n-cell Polycubes Proper in n-k Dimensions
A polyomino is an edge-connected set of squares on the 2-dimensional square lattice. Polyominoes and their higher-dimensional generalizations, polycubes, have been a fascinating subject, starting from recreational mathematics and ranging to fundamental questions in statistical physics, where they are called lattice animals.
The questions of finding or estimating the number A_d(n) of d-dimensional polycubes with a given number n of cells have challenged mathematicians, computer scientists, and theoretical physicists alike. The research in this area is characterized by interplay between computer methods on the one hand, and analytical and theoretical methods, on the other hand.
In particular, we consider polycubes with n cubes that span n-k dimensions, for a fixed k and for variable n. The number of these polycubes is denoted by DX(n,n-k), and explicit formulae for k=1 and k=2 are known. More recently, a formula for k=3 has been derived. It is based on a graph-theoretic model for polycubes, an exclusion-inclusion formula using various types of graph and tree patterns that can occur in polycubes and elaborate case distinctions. A simple formula for DX(n,n-k) for every k would yield a simple formula for A_d(n). However, carrying this approach beyond k=3 would create a case analysis that surpasses the patience of humans.
In my talk I will describe the theoretical framework we have created for computing the explicit formula for DX(n,n-k) for any ?fixed value of k, show how we used this framework to prove the known, yet unproven conjecture about the general form of the formula for a varying k, and overview our computer program which reaffirmed the known formulae for k = 2 and k = 3, and proved rigorously, for the first time, the formulae for k = 4 and k = 5.
This work was done jointly with Gill Barequet (Technion, Haifa).