אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

A polyomino of size n consists of n squares joined along their edges. A popular example is the computer game Tetris, which features polyominoes of size 4. A d-dimensional polycube of size n is a connected set of n d-dimentional cubes, where connectivity is through (d−1) dimensional faces. Fixed polycubes are usually considered identical if one can be translated into the other. In this research we focus on basic questions along the lines of: how many fixed d-dimentional polycubes of size n are there? In most cases, a simple closed formula for this number, usually denoted by A_d(n), is not known, and so other results are sought: A generating function, an estimation of their growth rate, an efficient counting algorithm, etc. The function A_2(n) is the “holy grail” of polyominoes enumeration research. Our research can be characterized by an interplay between computer methods, on the one hand, and analytical and theoretical methods, on the other hand. Many of our proofs are computer-assisted obtained by checking through numerous individual cases, and are too large to be directly verifiable by humans. Such proofs have become commonplace in combinatorics. In this work, we concerned ourselves with the problem of enumerating lattice animals: computing, or estimating, how many lattice animals exist for a given type or size. We investigated the problem in several directions: We improved the lower bound on the growth constant of polyominoes and showed, for the first time, that it is strictly greater than the mythical barrier of 4: the number of neighbours of a square on the 2-dimensional square grid. We believe that we were also able to show 4.59 as a new upper bound on this constant, improving upon Klarner and Rivest's upper bound of 4.65 from the 1970's. We consider similar shapes on the two-dimensional triangular lattice, which are called polyiamonds. We improved both the lower and upper bounds on the growth constant of polyiamonds, proving that it is bounded by 2.8424 from below and by 3.6050 from above. Finally, we study proper polycubes. A polycube is said to be proper in d dimensions if the convex hull of the centers of its cubes is d-dimensional. We developed a theoretical framework for computing the explicit formulae enumerating polycubes of size n which are proper in n-k dimensions, for a fixed value of k. The main contribution of this framework is that it enabled us to prove a conjecture about the general form of the formula for a general value of k. We have also used it to implement a 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.