Polygons

While self-avoiding polygons remain unsolved, a number of topologically restricted families of polygons have been solved; these fall into three categories:

• $3$-choice polygons,
• diagonally-convex directed polygons, and
• the many families of column-convex polygons.

Definition 8

• A $3$-choice polygon is a polygon whose perimeter obeys the $3$-choice walk rule (see above); i.e. the perimeter is constructed in the same manner as a $3$-choice walk, excepting that the walk must return to the origin (see figure 14).

• A polygon is diagonally-convex if its intersection with lines of the form, $x+y=k$ (with $k \in \mathbb{Z}$), is connected. A polygon is a diagonally-convex directed polygon if it is diagonally-convex and also a directed polyomino.

• A polygon is column-convex if its intersection with any vertical line is connected. The definition of row-convex is similar.

It is worth noting that while any column-convex polyomino is necessarily a polygon, a diagonally-convex polyomino may not be a polygon (the polyomino on the left of figure 10 is diagonally convex but not a polygon).

Figure 14: Examples of a $3$-choice polygon, a diagonally-convex directed polygon and a column-convex polygon. The perimeter of the $3$-choice polygon is a $3$-choice walk that returns to the origin (which is highlighted).

In the next chapter we give the definitions of all the column-convex families of polygons: column-convex polygons, directed column-convex polygons, bargraphs, fully convex polygons²³, directed convex polygons, staircase polygons, stacks, Ferrers diagrams and rectangles.

Diagonally convex directed polygons, $3$-choice polygons and the many families of column-convex polygons have all been enumerated according to their anisotropic perimeter (number of vertical and horizontal bonds) and area (see tables in the next chapter). Further, they have been enumerated by both of these parameters simultaneously; for example, we know that there are exactly $4$ column-convex polygons with an area of $3$, a horizontal perimeter of $4$ and a vertical perimeter of $4$ (these are the ``L'' shaped polyominoes in figure ). Almost all of these solutions rely on the same two methods:

• by splitting a polygon into two smaller polygons at a point where it is especially thin, one can construct equations for the generating function that can then (hopefully) be solved -- this method is sometimes referred to as ``wasp-waist factorisation''. A similar method consists of mapping polygons to words in algebraic languages and then using the grammar of that language to determine the generating function.
• by using a column-by-column construction, one can find a (solvable) recurrence or functional equation for column-convex polygons (diagonally convex directed polygons can be constructed diagonal-by-diagonal). This method was used by Temperley to enumerate the largest family of column-convex polygons according to their area [40] and is sometimes known as the ``Temperley method''; we describe this technique in chapter 5.

While all solved polygon models have been enumerated according to their area and (anisotropic) perimeter, there are very few results concerning the enumeration of polygons according to other parameters. One parameter of considerable importance in the modelling of random media is site-perimeter (see section 4.1 below). All the polygons which have been enumerated according to their site-perimeter are both row and column convex; in these cases the techniques used to take site-perimeter into account are the same as those used to enumerate perimeter and so the perimeter and site-perimeter solutions are of the same nature. When we consider polygons that are column-convex but not row-convex, we find that the site-perimeter and perimeter behave differently, and we can no longer use the same methods. In chapter 6 we use a variation of the column-by-column construction (which we describe in chapter 5), to extend site-perimeter enumeration results to the simplest family of non-convex polygons, bargraphs.

From the above discussion it should be clear that finding families of animals, polyominoes or polygons that we can actually solve is a non-trivial exercise. Guttmann and Enting [20] noticed that the anisotropic generating functions²⁴ of most solved statistical mechanical models have a very simple analytic structure, while those of unsolved models are considerably more complicated (we will be more precise about what we mean by this in chapter 3). They proposed that by examining the first few terms of the anisotropic generating function one could test the ``solvability'' of a model; in particular one could test if the generating function is likely to be expressible in terms of ``nice'' functions such as differentiably finite functions (see chapter 8). Applications of this technique show that many bond animal problems we would like to solve, including bond animals and self-avoiding polygons, are not solvable in terms of these nice functions [19,25].

In chapter 3 we describe a ``squashing'' technique, which we call haruspicy, that allows us to examine aspects of the analytic structure of anisotropic perimeter generating functions of bond-animals, regardless of whether the solution is known in closed form. For self-avoiding polygons (see chapter 8) we are able to use this technique to sharpen the numerical results of Guttmann and Enting's test into proof -- i.e. we prove that the anisotropic perimeter generating function of SAPs is not a differentiably finite function. In chapter 8 we describe a type of functional symmetry called reciprocity or inversion relations. We are able to demonstrate that a number of solved and unsolved polygon models satisfy such symmetries and we show that in certain favourable circumstances these symmetries can be used to solve the model.