On Minimal-Perimeter Lattice Animals

Abstract

A lattice animal is a connected set of cells on a lattice. The perimeter of a lattice animal A consists of all the cells that do not belong to A, but that have a least one neighboring cell of A. We consider minimal-perimeter lattice animals, that is, animals whose periemeter is minimal for all animals of the same area, and provide a set of conditions that are sufficient for a lattice to have the property that inflating all minimal-perimeter animals of a certain size yields (without repetitions) all minimal-perimeter animals of a new, larger size. We demonstrate this result for polyhexes (animals on the two-dimensional hexagonal lattice).

Cyvin S.J., Cyvin B.N., Brunvoll J. (1993) Enumeration of benzenoid chemical isomers with a study of constant-isomer series. In: Computer Chemistry, part of Topics in Current Chemistry book series, vol. 166. Springer, Berlin, Heidelberg (p. 117).

1 Introduction

An animal on a d-dimensional lattice is a connected set of lattice cells, where connectivity is through ($d{-}1$)-dimensional faces of the cells. Specifically, in two dimensions, connectivity is through lattice edges. Two animals are considered identical if one can be obtained from the other by translation only, without rotations or flipping. (Such animals are called “fixed” animals in the literature.)

Lattice animals attracted interest as combinatorial objects  [10] and as a model in statistical physics and chemistry  [17]. In this paper, we consider lattices in two dimensions, specifically, the hexagonal, triangular, and square lattices, where animals are called polyhexes, polyiamonds, and polyominoes, respectively. We focus on the application of our results to the hexagonal lattice, and explain how to make them applicable also to the triangular lattice.

Let $A^\mathcal {L}(n)$ denote the number of lattice animals of size n, that is, animals composed of n cells, on a lattice $\mathcal {L}$. A major research problem in the study of lattices is understanding the nature of $A^\mathcal {L}(n)$, either by finding a formula for it as a function of n, or by evaluating it for specific values of n. This problem is to this date still open for any nontrivial lattice. Redelmeier  [15] introduced the first algorithm for counting all polyominoes of a given size, with no polyomino being generated more than once. Later, Mertens  [14] showed that Redelmeier’s algorithm can be utilized for any lattice. The first algorithm for counting lattice animals without generating all of them was introduced by Jensen  [13]. Using his method, the number of animals on the 2-dimensional square, hexagonal, and triangular lattices were computed up to size 56, 46, and 75, respectively.

An important measure of lattice animals is the size of their perimeter (sometimes called “site perimeter”). The perimeter of a lattice animal is defined as the set of empty cells adjacent to the animal cells. This definition is motivated by models in statistical physics. In such discrete models, the plane or space is made of small cells (squares or cubes, respectively), and quanta of material or energy “jump” from a cell to a neighboring cell with some probability. Thus, the perimeter of a cluster determines where units of material or energy can move to, and guide the statistical model of the flow.

Fig. 1.

A polyomino $Q$ and its inflated polyomino $I(Q)$. Polyomino cells are colored gray, perimeter cells are colored white.

Asinowski et al.  [2, 3] provided formulae for polyominoes and polycubes with perimeter size close to the maximum possible. On the other extreme reside animals with the minimum possible perimeter size for their area. The study of polyominoes of a minimal perimeter dates back to Wang and Wang  [19], who gave an infinite sequence of cells on the square lattice, the first n of which (for any n) form a minimal-perimeter polyomino. Later, Altshuler et al.  [1], and independently Sieben  [16], studied the closely-related problem of the maximum area of a polyomino with p perimeter cells, and provided a closed formula for the minimum perimeter of an n-cell polyomino.

Recently, Barequet and Ben-Shachar  [4, 5] studied properties of minimal-perimeter polyominoes. A key notion in their findings is the inflation operation. Simply put, inflating a polyomino is creating the union of a polyomino and the set of its perimeter cells (see Fig. 1). Barequet and Ben-Shachar showed that inflating all the minimal-perimeter polyominoes of some size yields all the minimal-perimeter polyominoes of some larger size in a bijective manner. In this paper, we generalize this result to other lattices and find a sufficient set of conditions for such a bijection to exist.

In the literature, minimal-perimeter animals were studied also on other lattices. For animals on the triangular lattice (polyiamonds), the main result is due to Fülep and Sieben  [11], who characterized all the polyiamonds with maximum area for their perimeter, and provided a formula for the minimum perimeter of a polyiamond of size n. However, there has been much more intensive research of minimal-perimeter animals on the hexagonal lattice (polyhexes), mainly in the literature on organic chemistry. There has been a vast amount of work on molecules called benzenoid hydrocarbons. It is a known natural fact that molecules made of carbon atoms are structured as shapes on the hexagonal lattice, that is, exactly as polyhexes. Benzenoids hydrocarbons are made of only carbon and hydrogen atoms. In such a molecule, thecarbon atoms are arranged as a polyhex and the hydrogen atoms are arranged around the carbons, at the perimeter of the polyhex. The number of hydrogen atoms is exactly the size of the perimeter of the imaginary polyhex. Figure 2 shows a schematic drawing of Naphthalene (molecular formula $C_{10}H_8$), a simple benzenoid hydrocarbon made of 10 carbon atoms and 8 hydrogen atoms. Note that different configurations of atoms exist for the same molecular formula—these are called isomers. In the field of organic chemistry, a major goal is to enumerate all the different isomers of a given formula. In a series of papers (culminated in Reference  [9]), Dias provided the basic theory of the enumeration of benzenoids hydrocarbons.

Fig. 2.

The Naphthalene molecule ($C_{10} H_8$).

A comprehensive review of the subject is given by Brubvoll and Cyvin  [6]. Several other works  [7, 8, 12] also dealt with the properties and enumeration of such animals. Inflating is called by chemists circumscribing. For example, circumscribing the Naphthalene molecule yields a molecule known as Circumnaphthalene. In the chemistry literature, it is well known that inflating all isomers of some molecular formulae creates all isomers that correspond to another molecular formula. (The sequences of molecular formulae that have the same number of isomers created by circumscribing are known as constant-isomer series.) Although this fact is well known, to the best of our knowledge, no rigorous proof of it was ever given. This is exactly the analogue of a theorem proven by the authors of this paper for polyominoes  [4].

In this paper, we generalize the fact that inflation induces a bijection between sets of minimal-perimeter animals from the square lattice to other lattices, specifically, to the hexagonal lattice. By this, we prove the long-observed (but never proven) phenomenon of “constant-isomer chains,” that is, that inflating isomers of benzenoid hydrocarbon molecules (in our terminology, inflating minimum-perimeter polyhexes) yields all the isomers of a larger molecule.

Fig. 3.

A polyhex $Q$, its inflated polyhex $I(Q)$, and its deflated polyhex $D(Q)$.

2 Preliminaries

Let $\mathcal {L}$ be a lattice, and let $Q$ be an animal on $\mathcal {L}$. The perimeter of $Q$, denoted by $\mathcal {P}(Q)$, is the set of all empty lattice cells that are neighbors of at least one cell of $Q$. Similarly, the border of $Q$, denoted by $\mathcal {B}(Q)$, is the set of cells of $Q$ that are neighbors of at least one empty cell. The inflated version of $Q$ is defined as $I(Q) := Q\cup \mathcal {P}(Q)$. Similarly, the deflated version of $Q$ is defined as $D(Q) := Q\backslash \mathcal {B}(Q)$. These operations are demonstrated in Fig. 3.

Denote by $\epsilon ^\mathcal {L}(n)$ the minimum size (number of cells) of the perimeter of n-cell animals on $\mathcal {L}$, and by $M_n^\mathcal {L}$ the set of all minimal-perimeter n-cell animals on $\mathcal {L}$. Let $\mathcal {S}$ be the two-dimensional square lattice. Animals on $\mathcal {S}$ are usually called polyominoes. For this lattice, we know the following.

Theorem 1

[4, Thm. 4] $\left| M_n^\mathcal {S}\right| = \left| M_{n+\epsilon ^\mathcal {S}(n)}^\mathcal {S}\right|$ (for $n \ge 3$).

This theorem is a corollary of another theorem that states that the inflation operation induces bijections between sets of minimal-perimeter polyominoes. This is demonstrated in Fig. 4.

Fig. 4.

A demonstration of Theorem 1.

3 Minimal-Perimeter Animals

Our main result consists of a certain set of conditions, which is sufficient for minimal-perimeter animals to satisfy a claim similar to the one stated in Theorem 1. Throughout this section, we consider animals on some specific lattice $\mathcal {L}$.

3.1 A Bijection

Theorem 2

Consider the following set of conditions.

• (1) The function $\epsilon ^\mathcal {L}(n)$ is weakly monotone increasing.

• (2) There exists some constant $c\ge 0$, for which, for any minimal-perimeter animal $Q$, we have that $\left| \mathcal {P}(Q)\right| = \left| \mathcal {B}(Q)\right| + c$ and $\left| \mathcal {P}(I(Q))\right| \le \left| \mathcal {P}(Q)\right| +c$.

• (3) If $Q$ is a minimal-perimeter animal, then $D(Q)$ is a valid (connected) animal.

If all the above conditions hold for $\mathcal {L}$, then $\left| M_n^\mathcal {L}\right| = \left| M_{n+\epsilon ^\mathcal {L}(n)}^\mathcal {L}\right|$. If these conditions are not satisfied for only a finite amount of sizes of animals on $\mathcal {L}$, then the claim holds for all sizes greater than some nominal size $n_0$.    $\square$

Remark. Obviously, no lattice fulfills condition (2) with $c<0$, and only trivial lattices (e.g., the 1-dimensional lattice) fulfill it with $c=0$.

The remainder of this section is devoted to proving the theorem above. We begin with proving that inflation preserves perimeter minimality.

Lemma 1

If $Q$ is a minimal-perimeter animal, then $I(Q)$ is a minimal-perimeter animal as well.

Proof

Let $Q$ be a minimal-perimeter animal. Assume to the contrary that $I(Q)$ is not a minimal-perimeter animal, thus, there exists an animal $Q'$, such that $\left| Q'\right| = \left| I(Q)\right|$ and $\left| \mathcal {P}(Q')\right| < \left| \mathcal {P}(I(Q))\right|$. By Condition (2) of Theorem 2, we know that $\left| \mathcal {P}(I(Q))\right| \le \left| \mathcal {P}(Q)\right| + c$, thus, $\left| \mathcal {P}(Q')\right| < \left| \mathcal {P}(Q)\right| +c$, and since $Q'$ is a minimal-perimeter animal, we also know by the same condition that $\left| \mathcal {P}(Q')\right| = \left| \mathcal {B}(Q')\right| +c$, and, thus, that $\left| \mathcal {B}(Q')\right| < \left| \mathcal {P}(Q)\right|$. Consider now the animal $D(Q')$. Recall that $\left| Q'\right| = \left| I(Q)\right| =\left| Q\right| +\left| \mathcal {P}(Q)\right|$, hence, the size of $D(Q')$ is at least $\left| Q\right| +1$, and $\left| \mathcal {P}(D(Q'))\right| < \left| \mathcal {P}(Q)\right| = \epsilon ^\mathcal {L}(|Q|)$ (since the perimeter of $D(Q')$ is a subset of the border of $Q'$). This is a contradiction to Condition (1), which states that the sequence $\epsilon ^\mathcal {L}(n)$ is monotone increasing. Therefore, the animal $Q'$ cannot exist, and $I(Q)$ is a minimal-perimeter animal.    $\square$

We now proceed to demonstrate the effect of repeated inflation on the size of minimal-perimeter animals.

Lemma 2

The minimum size of the perimeter of animals of area $n+k\epsilon ^\mathcal {L}(n)+ck(k-1)/2$ (for $n > 1$ and any $k \in \mathbb {N}$) is $\epsilon (n)+ck$.

Proof

We repeatedly inflate a minimal-perimeter animal $Q$, whose initial size is n. The size of the perimeter of $Q$ is $\epsilon ^\mathcal {L}(n)$, thus, inflating it creates a new animal of size $n+\epsilon ^\mathcal {L}(n)$, and the size of the border of $I(Q)$ is $\epsilon ^\mathcal {L}(n)$, thus, by Condition (2), the size of the perimeter of $I(Q)$ is $\epsilon ^\mathcal {L}(n) + c$. By repeating this operation, the kth inflation step will increase the size of the animal by $\epsilon ^\mathcal {L}(n) + (k-1)c$ and will increase the size of the perimeter by c. Summing up these amounts yields the claim.    $\square$

Next, we prove that inflation preserves difference, that is, inflating two different minimal-perimeter animals (of equal or different sizes) always produces two different new animals. (This is not true for non-minimal-perimeter animals.)

Lemma 3

Let $Q_1,Q_2$ be two different minimal-perimeter animals. Then, regardless of whether or not $Q_1,Q_2$ have the same area, the animals $I(Q_1)$ and $I(Q_2)$ are different as well.

Proof

Assume to the contrary that $Q= I(Q_1) = I(Q_2)$, i.e., that $Q= Q_1 \cup \mathcal {P}(Q_1) = Q_2 \cup \mathcal {P}(Q_2)$. In addition, since $Q_1 \ne Q_2$, and since a cell cannot belong simultaneously to both an animal and to its perimeter, this means that $\mathcal {P}(Q_1) \ne \mathcal {P}(Q_2)$. The border of $Q$ is a subset of both $\mathcal {P}(Q_1)$ and $\mathcal {P}(Q_2)$, that is, $\mathcal {B}(Q) \subset \mathcal {P}(Q_1) \cap \mathcal {P}(Q_2)$. Since $\mathcal {P}(Q_1) \ne \mathcal {P}(Q_2)$, we have that either $\left| \mathcal {B}(Q)\right| < \left| \mathcal {P}(Q_1)\right|$ or $\left| \mathcal {B}(Q)\right| < \left| \mathcal {P}(Q_2)\right|$; assume without loss of generality the former case. Now, consider the animal $D(Q)$. Its size is $\left| Q\right| -\left| \mathcal {B}(Q)\right|$. The size of $Q$ is $\left| Q_1\right| +\left| \mathcal {P}(Q_1)\right|$, thus, $\left| D(Q)\right| > \left| Q_1\right|$, and since the perimeter of $D(Q)$ is a subset of the border of $Q$, we have that $\left| \mathcal {P}(D(Q))\right| < \left| \mathcal {P}(Q_1)\right|$. However, $Q_1$ is a minimal-perimeter animal, which is a contradiction to Condition (1) of Theorem 2, which states that $\epsilon ^\mathcal {L}(n)$ is monotone increasing.    $\square$

To complete the cycle, we also prove that for any minimal-perimeter animal $Q\in M^\mathcal {L}_{n+\epsilon ^\mathcal {L}(n)}$, there is a minimal-perimeter source in $M^\mathcal {L}_n$, i.e., an animal $Q'$ whose inflation yields $Q$. Specifically, this animal is $D(Q)$.

Lemma 4

For any $Q\in M^\mathcal {L}_{n+\epsilon ^\mathcal {L}(n)}$, we also have that $I(D(Q)) = Q$.

Proof

Since $Q\in M^\mathcal {L}_{n+\epsilon (n)}$, we have by Lemma 2 that $\left| \mathcal {P}(Q)\right| = \epsilon (n)+c$. Combining this with the equality $\left| \mathcal {P}(Q)\right| = \left| \mathcal {B}(Q)\right| +c$, we obtain that $\left| \mathcal {B}(Q)\right| = \epsilon (n)$, thus, $\left| D(Q)\right| = n$ and $\left| \mathcal {P}(D(Q))\right| \ge \epsilon (n)$. Since the perimeter of $D(Q)$ is a subset of the border of $Q$, and $\left| \mathcal {B}(Q)\right| = \epsilon (n)$, we conclude that the perimeter of $D(Q)$ and the border of $Q$ are the same set of cells, and, thus, $I(D(Q)) = Q$.    $\square$

Let us now wrap up the proof of Theorem 2. In Lemma 1 we have shown that for any minimal-perimeter animal $Q\in M_n$, we have that $I(Q) \in M^\mathcal {L}_{n+\epsilon ^\mathcal {L}(n)}$. In addition, Lemma 3 states that the inflation of two different minimal-perimeter animals results in two other different minimal-perimeter animals. Combining the two lemmata, we obtain that $\left| M^\mathcal {L}_n\right| \le \left| M^\mathcal {L}_{n+\epsilon ^\mathcal {L}(n)}\right|$. On the other hand, in Lemma 4 we have shown that if $Q\in M^\mathcal {L}_{n+\epsilon ^\mathcal {L}(n)}$, then $I(D(Q)) = Q$, and, thus, for any animal in $M^\mathcal {L}_{n+\epsilon ^\mathcal {L}(n)}$, there is a unique source in $M^\mathcal {L}_n$ (specifically, $D(Q)$), whose inflation yields $Q$. Hence, $\left| M^\mathcal {L}_n\right| \ge \left| M^\mathcal {L}_{n+\epsilon ^\mathcal {L}(n)}\right|$. Combining the two relations, we conclude that $\left| M^\mathcal {L}_n\right| = \left| M^\mathcal {L}_{n+\epsilon ^\mathcal {L}(n)}\right|$.

3.2 Inflation Chains

Theorem 2 implies that there exist infinitely-many chains of sets of minimal-perimeter animals, each one obtained from the previous one by inflation, while the cardinalities of all sets in a single chain are identical. Obviously, there are sets of minimal-perimeter animals that are not created by inflating any other set. We call the size of animals in such sets an inflation-chain root. Using the definitions and proofs in the previous section, we are able to characterize which sizes are the inflation-chain roots. The result is stated in the following theorem, and its full proof is given in the full version of the paper.

Theorem 3

Let $\mathcal {L}$ be a lattice for which the three premises of Theorem 2 are satisfied, and, in addition, the following condition holds.

• (4) The inflation operation preserves (for an animal) the property of having a maximum size for a given perimeter.

Then, if n is the minimum animal area for a minimal-perimeter size p, or equivalently, if there exists a perimeter size p, such that $n = \min \left\{ n \in \mathbb {N}\mid \epsilon ^{\mathcal {L}}(n) = p\right\}$, then n is an inflation-chain root.    $\square$

4 Application to Polyhexes

Denote the two-dimensional hexagonal lattice by $\mathcal {H}$. In this section, we show that the conditions of Theorem 2 hold for the lattice $\mathcal {H}$.

4.1 Condition 1: Monotonicity

Condition (1) was proven independently, first by Vainsencher and Bruckstien  [18], and later by Fülep and Sieben  [11]. We will use the latter, stronger proof which also provides a formula for $\epsilon ^\mathcal {H}(n)$.

Theorem 4

[11, Thm. 5.12] $\epsilon ^\mathcal {H}(n) = \left\lceil \sqrt{12n-3}\;\right\rceil +3$.    $\square$

Clearly, the function $\epsilon ^\mathcal {H}(n)$ is weakly monotone increasing.

4.2 Condition 2: Constant Inflation

To show that Condition (2) holds, we will analyze the different patterns that may appear in the border and perimeter of minimal-perimeter polyhexes. We can classify every border or perimeter cell by one of exactly 24 patterns, distinguished by the number and positions of their adjacent occupied cells. The 24 existing patterns are shown in Fig. 5.

Fig. 5.

All possible patterns (up to symmetric cases) of border (first row) and perimeter (second row) cells. The gray cells are polyhex cells, while the white cells are perimeter cells. Each pattern consists of a cell in the middle, and the possible distribution of cells surrounding it.

Asinowski et al.  [2] defined the excess of a perimeter cell to be the number of adjacent occupied cell minus one. We extend this definition to border cells, and, in a similar manner, we define the excess of a border cell as the number of adjacent empty cells minus one. Following these definitions, we define the perimeter excess of a polyhex $Q$, $e_P(Q)$, to be the sum of excesses over all perimeter cells of $Q$, and similarly, the border excess of $Q$, $e_B(Q)$, is defined to be the sum of excesses over all border cells of $Q$.

The following formula is universal for all polyhexes.

Lemma 5

For every polyhex $Q$, we have that

$$\begin{aligned} \left| \mathcal {P}(Q)\right| + e_P(Q) = \left| \mathcal {B}(Q)\right| + e_B(Q) \end{aligned}$$

(1)

Proof

Consider the (one or more) polygons bounding the polyhex $Q$. The two sides of the equation are equal to the total length of the polygon(s) in terms of polyhex edges. Indeed, this length can be computed by iterating over either the border or the perimeter cells of $Q$. In both cases, each cell contributes one edge plus its excess to the total length. The claim follows.    $\square$

Our next goal is to express the excess of a polyhex $Q$ as a function of the numbers of cells of $Q$ of each pattern. We denote the number of cells of a specific pattern in $Q$ by $\#\square$, where ‘$\square$’ is one of the 24 patterns listed in Fig. 5. The excess (either border or perimeter excess) of Pattern $\square$ is denoted by $e(\square )$. (For simplicity, we omit the dependency on $Q$ in the notations of $\#\square$ and $e(\square )$. This should be understood from the context.) The border excess can be expressed as $e_B(Q) = \sum _{\square \in \{a,\dots ,l\}} e(\square )\#\square$, and, similarly, the perimeter excess can be expressed as $e_P(Q) = \sum _{\square \in \{o,\dots ,z\}} e(\square )\#\square$. By plugging these equations into Eq. (1), we obtain that

$$\begin{aligned} \left| \mathcal {P}(Q)\right| + \sum _{\square \in \{o,\dots ,z\}} e(\square )\#\square = \left| \mathcal {B}(Q)\right| + \sum _{\square \in \{a,\dots ,l\}} e(\square )\#\square ~. \end{aligned}$$

(2)

The next step of proving the second condition is showing that minimal-perimeter polyhexes cannot contain some of the 24 patterns. This will simplify Eq. (2).

Lemma 6

No minimal-perimeter polyhex contains holes.

Proof

Assume to the contrary that there exists a minimal-perimeter polyhex $Q$ which contains one or more holes, and let $Q'$ be the polyhex obtained by filling one of the holes in $Q$. Clearly, $|Q'| > |Q|$, and by filling the hole we eliminated some perimeter cells and did not create new perimeter cells. Hence, $\left| \mathcal {P}(Q')\right| < \left| \mathcal {P}(Q)\right|$. This contradicts the fact that $\epsilon ^\mathcal {H}(n)$ is monotone increasing, as implied by Theorem 4.    $\square$

Another important observation is that minimal-perimeter polyhexes tend to be “compact.” We formalize this observation in the following lemma.

A bridge is a cell whose removal unites two holes or renders the polyhex disconnected (specifically, Patterns (b), (d), (e), (g), (h), (j), and (k)). Similarly, a perimeter bridge is an empty cell whose addition to the polyhex creates a hole in the latter (specifically, Patterns (p), (r), (s), (u), (v), (x), and (y)).

Lemma 7

Minimal-perimeter polyhexes contain neither bridges nor perimeter bridges.    $\square$

The proof is given in the full version of the paper.

As a consequence of Lemma 6, Pattern (o) cannot appear in any minimal-perimeter polyhex. In addition, Lemma 7 tells us that the Border Patterns (b), (d), (e), (g), (h), (j), and (k), as well as the Perimeter Patterns (p), (r), (s), (u), (v), (x), and (y) cannot appear in any minimal-perimeter polyhex. (Note that the central cells in Patterns (b) and (p) are not bridges by themselves, however, the adjacent cells are bridges.) Finally, Pattern (a) appears only in the singleton cell (the unique polyhex of size 1), which can be disregarded. Ignoring all the patterns mentioned above, we conclude that

$$\begin{aligned} \left| \mathcal {P}(Q)\right| + 3\#q + 2\#t + \#w = \left| \mathcal {B}(Q)\right| + 3\#c + 2\#f + \#i. \end{aligned}$$

(3)

Note that Patterns (l) and (z) have excess 0, and, thus, although they may appear in minimal-perimeter polyhexes, they do not appear in the equation.

Consider a polyhex having only the six feasible patterns (those that appear in Eq. (3)). Let us examine the single polygon bounding the polyhex, specifically, let us count the number of vertices and the sum of internal angles which appear in this polygon as a function of the numbers of appearances of the different patterns. We are able to show that the total number of vertices is

$$ 3\#c+2\#f+\#i+3\#q+2\#t+\#w, $$

and that the sum of internal angles is

$$\begin{aligned} (3\#c+2\#f+\#i)120^{\circ } + (3\#q+2\#t+\#w)240^{\circ }. \end{aligned}$$

(4)

The full details of these calculations are given in the full version of the paper. On the other hand, it is known that the sum of internal angles is equal to

$$\begin{aligned} (3\#c+2\#f+\#i+3\#q+2\#t+\#w-2)180^{\circ }. \end{aligned}$$

(5)

Equating the terms in Formulae (4) and (5), we obtain that

$$ 3\#c+2\#f+\#i = 3\#q+2\#t+\#w + 6. $$

Plugging this into Eq. (3), we conclude that $\left| \mathcal {P}(Q)\right| = \left| \mathcal {B}(Q)\right| + 6$, as required.

We also need to show the second part of Condition (2), that is, that if $Q$ is a minimal-perimeter polyhex, then $\left| \mathcal {P}(I(Q))\right| \le \left| \mathcal {P}(Q)\right| + 6$. To this aim, note that $\mathcal {B}(I(Q)) \subset \mathcal {P}(Q)$, thus, it is sufficient to show that $\left| \mathcal {P}(I(Q))\right| \le \left| \mathcal {B}(I(Q))\right| + 6$. Obviously, Eq. (2) holds for the polyhex $I(Q)$, thus, in order to prove the relation, we only need to show that there are no bridges in $I(Q)$. The proof is given in the full version of the paper. We wrap up this discussion with the following lemma.

Lemma 8

If $Q$ is a minimal-perimeter polyhex, then $I(Q)$ does not contain any polyhex bridge.    $\square$

4.3 Condition 3: Deflation Resistance

The last condition which we need to show states that deflating a minimal-perimeter polyhex results in another (smaller) valid polyhex. The intuition behind this condition is that a minimal-perimeter polyhex is “compact,” having a shape which does not become disconnected by deflation. The next lemma formalizes this notion of compactness. The proof is provided in the full version of the paper.

Lemma 9

For any minimal-perimeter polyhex $Q$, the shape $D(Q)$ is a valid polyhex.    $\square$

To conclude, we have shown that all the premises of Theorem 2 are satisfied for the hexagonal lattice, and, thus, inflating a set of all the minimal-perimeter polyhexes of a certain size yields another set of minimal-perimeter polyhexes of another, larger size. This result is demonstrated in Fig. 6.

Fig. 6.

A demonstration of Theorem 2 for polyhexes. The top row contains all polyhexes (up to rotations and reflections) in $M^\mathcal {H}_9$ (minimal-perimeter polyhexes of area 9), while the bottom row contains their inflated versions, all members of $M^\mathcal {H}_{23}$.

We also characterized inflation-chain roots of polyhexes. As is mentioned above, the premises of Theorem 3 are satisfied for polyhexes  [16, 18], and, thus, the inflation-chain roots are those which have the minimum size for a given minimal-perimeter size. An easy consequence of Theorem 4 is that the formula $\left\lfloor \frac{(p-4)^2}{12}+\frac{5}{4}\right\rfloor$ generates all these inflation-chain roots. This result is demonstrated in Fig. 7.

Fig. 7.

The relation between the minimum perimeter of polyhexes, $\epsilon ^\mathcal {H}(n)$, and the inflation-chain roots. The points represent the minimum perimeter of a polyhex of size n, and sizes which are inflation-chain roots are colored in red. The arrows show the mapping between sizes of minimal-perimeter polyhexes (induced by the inflation operation).

5 Polyiamonds

Polyiamonds are sets of edge-connected triangles on the regular triangular lattice, which is made of two types of cells. Due to this complication, inflating a minimal-perimeter polyiamond does not necessarily result in a minimal-perimeter polyiamond. Indeed, the second condition of Theorem 2 does not hold for polyiamonds. This fact is not surprising, since inflating minimal-perimeter polyiamonds creates “jagged” polyiamonds, which do not have a minimal perimeter (see Fig. 8(b)).

Fig. 8.

Inflating polyiamonds. The polyiamond $Q$ is of minimum perimeter, but $I(Q)$ is not. However, the polyiamond $I^*(Q)$, obtained by adding to $Q$ all the cells sharing a vertex with $Q$, is a minimal-perimeter polyiamond.

However, we can fix this situation by modifying the definition of the perimeter of a polyiamond so that the perimeter will include all cells that share a vertex (instead of an edge) of the (boundary of the) polyiamond. Theorem 2 holds under the new definition. The reason for this is surprisingly simple: The modified definition merely mimics the inflation of animals on the graph dual to that of the triangular lattice. (Recall that graph duality maps vertices to faces (cells), and vice versa, and edges to edges.) However, the dual of the triangular lattice is the hexagonal lattice, for which we have already shown in Sect. 4 that all the premises of Theorem 2 hold. Thus, applying the modified inflation operator ($I^*(\cdot )$) to the triangular lattice induces a bijection between sets of minimal-perimeter polyiamonds. This operation is demonstrated in Fig. 8.

6 Conclusion

In this paper, we have generalized a result which states that inflation induces a bijection between sets of minimal-perimeter polyominoes, to any lattice satisfying three conditions. We have shown that this generalization holds for the hexagonal lattice, and in some sense (with a modified definition of perimeter) also for the triangular lattice. The most important contribution of this paper is providing a proof for this phenomenon for polyhexes, which was observed in the chemistry literature more than 30 years ago but was never proven.

However, we do not believe that this set of conditions is necessary. Empirically, it seems that by inflating all the minimal-perimeter polycubes (animals on the 3-dimensional cubical lattice) of a given size, we obtain all the minimal-perimeter polycubes of some larger size. However, Condition (2) does not hold for this lattice. Moreover, we believe that as stated, Theorem 2 applies only to 2-dimensional lattices! A simple conclusion from Lemma 2 is that if the premises of Theorem 2 hold for animals on a lattice $\mathcal {L}$, then $\epsilon ^\mathcal {L}(n) = \varTheta (\sqrt{n})$. We find it is reasonable to assume that for a d-dimensional lattice $\mathcal {L}_d$, the relation between the size of a minimal-perimeter animal and its perimeter is roughly equal to the relation between a d-dimensional sphere and its surface area. Hence, we conjecture that $\epsilon ^{\mathcal {L}_d}(n) = \varTheta (n^{\frac{d-1}{d}})$, and, thus, Theorem 2 does not hold in higher dimensions.