|
Abstract:
|
Subject of this doctoral thesis is the application of algebraic techniques on one of the
central topics of combinatorics and discrete geometry - polyomino tiling. Polyomino tilings
are interesting not only to mathematicians, but also to physicists and biologists, and they
can also be applied in computer science. In this thesis we put some emphasis on possibility
to solve special class of tiling problems, that are invariant under the action of nite group,
by using theory of Gr obner basis for polynomial rings with integer coe cients. Method
used here is re
ecting deep connection between algebra, geometry and combinatorics.
Original scienti c contribution of this doctoral thesis is, at the rst place, in developing
a techniques which enable us to consider not only ordinary Z?tiling problems in
a lattice but the problems of tilings which are invariant under some subgroups of the
symmetry group of the given lattice. Besides, it provides additional generalizations, originally
provided by famous mathematicians J. Conway and J. Lagarias, about tiling of the
triangular region in hexagonal lattice.
Here is a summary of the content of the theses. In the rst chapter we give an
exposition of the Gr obner basis theory. Especially, we emphasize Gr obner basis for polynomial
rings with integer coe cients. This is because, in this thesis, we use algorithms
for determining Gr obner basis for polynomials with integer coe cients. Second chapter
provides basic facts about regular lattices in the plane. Also, this chapter provides some
fundamental terms of polyomino tiling in the square and hexagonal lattice.
Third chapter of this thesis is about studying Ztilings in the square lattice, which are
invariant under the subgroup G of the group of all isometric transformations of the lattice
which is generated by the central symmetry. One of the steps to resolve this problem was
to determine a ring of invariants PG and its generators and relations among them. We
use Gr obner basis theory to achieve this.
Forth chapter covers the analysis of Ztilings in the hexagonal lattice which are symmetric
with respect to the rotation of the plane for the angle of 120 . Main result of the
fourth chapter is the theorem which gives conditions for symmetric tiling of the triangular
region in plane TN, where N is the number of hexagons on each side of triangle.
This theorem is one of the possible generalizations of the well known result, provided by
Conway and Langarias.
Fifth chapter provides another generalization of Conway and Lagarias result, but this
time it is about determining conditions of tiling of triangular region TN in the hexagonal
lattice not only with tribones, but with nbones. nbone is basic shape of of n connected
cells in the hexagonal lattice, where n is arbitrary integer. |