Polygons, Polyominoes and Polycubes (Lecture Notes in Physics, 775)

The problem of counting the number of self-avoiding polygons on a square grid, - therbytheirperimeterortheirenclosedarea,is aproblemthatis soeasytostate that, at ?rst sight, it seems surprising that it hasn’t been solved. It is however perhaps the simplest member of a large class of such problems that have resisted all attempts at their exact solution. These are all problems that are easy to state and look as if they should be solvable. They include percolation, in its various forms, the Ising model of ferromagnetism, polyomino enumeration, Potts models and many others. These models are of intrinsic interest to mathematicians and mathematical physicists, but can also be applied to many other areas, including economics, the social sciences, the biological sciences and even to traf?c models. It is the widespread applicab- ity of these models to interesting phenomena that makes them so deserving of our attention. Here however we restrict our attention to the mathematical aspects. Here we are concerned with collecting together most of what is known about polygons, and the closely related problems of polyominoes. We describe what is known, taking care to distinguish between what has been proved, and what is c- tainlytrue,but has notbeenproved. Theearlierchaptersfocusonwhatis knownand on why the problems have not been solved, culminating in a proof of unsolvability, in a certain sense. The next chapters describe a range of numerical and theoretical methods and tools for extracting as much information about the problem as possible, in some cases permittingexactconjecturesto be made.

This unique book gives a comprehensive account of new mathematical tools used to solve polygon problems.

In the 20th and 21st centuries, many problems in mathematics, theoretical physics and theoretical chemistry – and more recently in molecular biology and bio-informatics – can be expressed as counting problems, in which specified graphs, or shapes, are counted.

One very special class of shapes is that of polygons. These are closed, connected paths in space. We usually sketch them in two-dimensions, but they can exist in any dimension. The typical questions asked include "how many are there of a given perimeter?", "how big is the average polygon of given perimeter?", and corresponding questions about the area or volume enclosed. That is to say "how many enclosing a given area?" and "how large is an average polygon of given area?" Simple though these questions are to pose, they are extraordinarily difficult to answer. They are important questions because of the application of polygon, and the related problems of polyomino and polycube counting, to phenomena occurring in the natural world, and also because the study of these problems has been responsible for the development of powerful new techniques in mathematics and mathematical physics, as well as in computer science. These new techniques then find application more broadly.

The book brings together chapters from many of the major contributors in the field. An introductory chapter giving the history of the problem is followed by fourteen further chapters describing particular aspects of the problem, and applications to biology, to surface phenomena and to computer enumeration methods.