TR#: | MSC-2018-18 |

Class: | MSC |

Title: | Two Researches on Lattice Animals |

Authors: | Yufei Zheng |

Supervisors: | Gill Barequet |

Currently accessibly only within the Technion network | |

Abstract: | Lattice animals are connected subgraphs of a lattice, where Fixed lattice animals are considered identical if one can be translated into the other. The fundamental combinatorial problem concerning lattice animals is “How many animals with n cells are there?” To this end, we consider two types of lattices, the d-dimensional hypercubic lattice and the two-dimensional triangular lattice, where the animals are frequently referred to as d-dimensional polycubes and polyiamonds, respectively. Since no general analytic formula for the number of animals is known for any nontrivial lattice, in this thesis, we focus on both driving formulae and understanding the growth constants.
We investigate formulae enumerating d-dimensional polycubes by volume and dimension with a fixed deviation from the maximum possible perimeter. Aside from the explicit formulae, a general framework for deriving such formulae is proposed. We further prove that for any fixed dimension d, the generating function that enumerates polycubes with a fixed defect with respect to their volume, is rational. Moreover, its denominator is a product of cyclotomic polynomials. In this thesis we also suggest a nontrivial extension of a concatenation argument for improving the lower bound on the growth constant of polyiamonds. However, the proposed extension is based on a reasonable yet unproven assumption. |

Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2018/MSC/MSC-2018-18), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2018

To the main CS technical reports page