# Extremal $\\{p,q\\}$-Animals

Greg Malen  Department of Mathematics, Union College, Schenectady, NY, United
States<EMAIL_ADDRESS>,  Érika Roldán  Zentrum Mathematik, TU München,
Garching b. München, Germany<EMAIL_ADDRESS>and  Rosemberg Toalá-
Enríquez  Adjunct Researcher, Topological Data Analysis Group, Center for
research in Mathematics, Guanajuato, México<EMAIL_ADDRESS>
###### Abstract.

An animal is a planar shape formed by attaching congruent regular polygons,
known as tiles, along their edges. In this paper, we study extremal animals
defined on regular tessellations of the plane. In 1976, Harary and Harborth
studied animals in the Euclidean cases, finding extremal values for their
vertices, edges, and tiles, when any one of these parameters is fixed. Here,
we generalize their results to hyperbolic animals. For each hyperbolic
tessellation, we exhibit a sequence of spiral animals and prove that they
attain the minimal numbers of edges and vertices within the class of animals
with $n$ tiles. In their conclusions, Harary and Harborth also proposed the
question of enumerating extremal animals with a fixed number of tiles. This
question has previously only been considered for Euclidean animals. As a first
step in solving this problem, we find special sequences of extremal animals
that are unique extremal animals, in the sense that any animal with the same
number of tiles which is distinct up to isometries can’t be extremal.

###### Key words and phrases:

Extremal combinatorics, enumerative combinatorics, polyforms, polyominoes,
polyiamonds, hexiamonds, animals, hyperbolic tessellations, isoperimetric
inequalities.
* See [20] for our interactive applets to explore extremal animals and their graph parameters.

###### 2020 Mathematics Subject Classification:

00A69, 05A16, 05A20, 05B50, 52B60, 52C05, 05C07, 05C10, 52C20, 05D99

##  1\. Introduction

An _animal_ is a planar shape with connected interior formed by gluing
together a finite number of congruent regular polygons along their edges.
Here, we study animals that have extremal combinatorial properties such as
having maximally many shared (or interior) edges for a given number of
polygons. We refer to animals attaining these optimal values as _extremal
animals_. In the Euclidean plane, extremal animals have been well studied and
it is known that they exhibit interesting geometric and combinatorial
properties such as being isoperimetric [7], giving contact numbers for optimal
disk packing configurations [8], and providing the right shape to produce
animals with maximally many holes [12, 17, 18, 19].

In the hyperbolic plane, combinatorial and geometric properties of extremal
animals have not been examined as closely. However, the relevance of extremal
animals in this setting to other extremal combinatorial problems has already
been established. These include optimal disk packing problems [4], the
calculation of Cheeger constants [9], the establishment of the exponential
growth constant of regular hyperbolic tessellations [13], and the
implementation of algorithms to sample certain hyperbolic animals to
approximate hyperbolic percolation thresholds [22].

Recently, extremal hyperbolic animals have been used to model and study
structures in applied mathematics, such as in crystallography theory for
materials with hyperbolic symmetries [3], and in the architecture of circuit
quantum electrodynamics [14]. More generally, models based on hyperbolic
tessellations have also been used in areas such as Bloch band theory in
physics [16], and in quantum error correcting and quantum storage codes [5,
10], among others. Therefore, having a better understanding of extremal
hyperbolic animals might lead to interesting insights, results, techniques,
and new research questions in these areas.

The families of animals that we study in this paper are formed by finite
subsets of tiles of regular Euclidean and hyperbolic tessellations. These
tessellations can be parameterized using the Schläfli symbol $\\{p,q\\}$,
where $p$ denotes the number of sides of the regular polygon forming the
tessellation and $q$ is the number of edges or tiles meeting at each vertex.
It is well known that if $(p-2)(q-2)>4$, $=4$, or $<4$, then the tessellation
corresponds to the geometry of the hyperbolic plane, the Euclidean plane, or
the sphere, respectively. We call an animal living in a
$\\{p,q\\}$-tessellation a $\\{p,q\\}$-animal. The most well-known families of
animals are those living in the Euclidean tessellations, namely for
$\\{p,q\\}$ either $\\{3,6\\}$, $\\{4,4\\}$, or $\\{6,3\\}$. Formed by
triangles, squares, or hexagons, respectively, these animals are also more
commonly known as polyiamonds, polyominoes, and polyhexes in the literature.

In 1976 [7], Harary and Harborth studied extremal animals in the three
Euclidean cases. More specifically, they gave algebraic expressions and bounds
for the number of interior, exterior, and total numbers of both vertices and
edges that an animal with a fixed number of tiles can have. Then they
constructed a family of spiral animals which attain optimal values. Here, we
extend Harary and Harborth’s analysis to extremal hyperbolic animals. First,
we define and analyze analogous sequences of spiral $\\{p,q\\}$-animals for
$(p-2)(q-2)\geq 4$ and provide algebraic expressions for the number of
vertices and edges in terms of a particular recursive sequence of integers.
Then we prove that these spiral $\\{p,q\\}$-animals are indeed extremal. As a
corollary of our results, we recover the formulas derived in [7] for the
Euclidean cases.

We also explore enumeration of extremal hyperbolic animals. Exact enumeration
of $\\{p,q\\}$-animals is only known for a few $\\{p,q\\}$ pairs, and even
then only for animals with a very small number of tiles. For instance, the
number of fixed $\\{4,4\\}$-animals with $n$ tiles is only known for $n\leq
56$ [11]; and otherwise very little is known (see, for example, the entries of
the OEIS A001207, A001420, A000228, A000577, A119611 [24] for values in the
$\\{3,6\\}$-, $\\{6,3\\}$-, and $\\{4,5\\}$-tessellations). In the particular
case of Euclidean animals, there are also asymptotic results and computational
approximations that give a better understanding of the problem of animal
enumeration [1, 2, 21, 23]. In their closing thoughts in [7], Harary and
Harborth raised the question of enumeration of extremal animals with $n$
tiles. Surprisingly, this problem has remained largely unexplored, and it has
been completely solved only for $\\{4,4\\}$-animals [15]. Before now, nothing
was known about the enumeration of extremal hyperbolic animals. As a
consequence of our main results, for all $\\{p,q\\}$ we find special sequences
of extremal animals that are unique extremal animals, in the sense that any
animal with the same number of tiles which is distinct up to isometries can’t
be extremal.

###  1.1. Main Results

We begin by analyzing a sequence of layered animals, which we use as
benchmarks for computing extremal values. These layered animals will attain
extremal values, but more significantly they provide context for keeping track
of how each subsequent tile affects all of the graph parameters in play.

######  Remark 1.1.

Note that in a $\\{p,q\\}$-animal, a vertex can have up to $q$ incident tiles.
If it has fewer than $q$ incident tiles, it is necessarily a perimeter vertex.
If it has a full set of $q$ incident tiles, it is an interior vertex, and we
say that it is _saturated_.

######  Definition 1.2.

We denote by $A_{p,q}(1)$ the animal with only one $p$-gon. We construct
$A_{p,q}(k)$ from $A_{p,q}(k-1)$ by adding precisely the tiles needed to
saturate all perimeter vertices of $A_{p,q}(k-1)$. The new tiles are called
the _$k$ -th layer_ of the structure. We call $A_{p,q}(k)$ the _complete
$k$-layered $\\{p,q\\}$-animal_.

Figure 1. Left: $A_{p,q}(3)$ for $\\{p,q\\}=\\{4,4\\}$. Right: $A_{p,q}(3)$
for $\\{p,q\\}=\\{4,5\\}$. The degree of each perimeter vertex–the number of
edges that are incident to the vertex–is written next to it. The case
$\\{4,5\\}$ is hyperbolic, and it is drawn in the Poincaré disk.

######  Theorem 1.3.

Denote by $\check{v}(k)$, $\check{e}(k)$, and $\check{n}(k)$ the number of
vertices, edges, and tiles, respectively, of the complete $k$-layered
$\\{p,q\\}$-animal $A_{p,q}(k)$. Let $t=(p-2)(q-2)-2$ and
$\alpha=\frac{t+\sqrt{t^{2}-4}}{2}$, then

  1. (1)

For t=2, we have Euclidean animals, and they satisfy

$\displaystyle\check{v}(k)$ $\displaystyle=pk^{2},$
$\displaystyle\check{e}(k)$
$\displaystyle=pk\left(\frac{q}{2}k-\frac{q}{2}+1\right),$
$\displaystyle\check{n}(k)$
$\displaystyle=1+\frac{p(q-2)}{2}k^{2}-\frac{p(q-2)}{2}k.$

  2. (2)

For $t>2$, we have hyperbolic animals, and they satisfy

$\displaystyle\check{v}(k)$
$\displaystyle=\frac{p}{t-2}\left(\alpha^{k}+\frac{1}{\alpha^{k}}-2\right),$
$\displaystyle\check{e}(k)$
$\displaystyle=\frac{p}{(\alpha-1)\sqrt{t^{2}-4}}\left((\alpha+q-1)\alpha^{k}+\frac{\alpha
q-\alpha+1}{\alpha^{k}}-q(\alpha+1)\right),$ $\displaystyle\check{n}(k)$
$\displaystyle=1+\frac{p(q-2)}{(\alpha-1)\sqrt{t^{2}-4}}\left(\alpha^{k}+\frac{1}{\alpha^{k-1}}-\alpha-1\right).$

We also find algebraic expressions in Equation (3.5) for the following graph
parameters: the number of interior vertices, perimeter edges, and interior
edges of $A_{p,q}(k)$, denoted respectively by $\check{v}_{int}(k)$,
$\check{e}_{1}(k)$, $\check{e}_{2}(k)$.

For $t>2$, we get as a corollary that the parameters of $A_{p,q}(k)$ grow
exponentially; as expected from the properties of hyperbolic geometry. The
exponential growth rate of these parameters is governed by the constant
$\alpha>1$.

######  Corollary 1.4.

Let $t=(p-2)(q-2)-2\geq 2$ and $\alpha=\frac{t+\sqrt{t^{2}-4}}{2}$. Then

$\lim_{k\to\infty}\check{v}(k+1)/\check{v}(k)=\alpha,$

and the same limit is true for the rest of the graph parameters listed in
Theorem 1.3.

Some of the recursive formulas for the complete layered sequence $A_{p,q}(k)$
in Theorem 1.3 were independently computed and used as a tool for
understanding geometric and combinatorial properties of the
$\\{p,q\\}$-tessellations. However, the extremality of these values was not
previously examined.

For instance, in [9], Higuchi and Shirai use the layered $A_{p,q}(k)$
structures to compute the Cheeger constant of the infinite graph of the
$\\{p,q\\}$-tessellations. Specifically, they give recursive computations for
$\check{v}(k)$ and a value equivalent to the number of tiles in a layer, i.e.,
$\check{n}(k)-\check{n}(k-1)$. Using these values they proved that the Chegeer
constant of the $\\{p,q\\}$-tessellation, defined by

$\inf\left\\{\frac{|E(\partial_{v}W)|}{\text{vol}(W)}:W\text{ is a finite
subgraph}\right\\},$

is equal to the limit of the corresponding values for $A_{p,q}(k)$ as
$k\to\infty$. Here, $|E(\partial_{v}W)|$ is the number of edges connecting $W$
with its complement, and vol$(W)=\sum_{x\in W}deg(x)$.

The $A_{p,q}(k)$ serve as a discrete analogue of balls of radius $k$ centered
at $A_{p,q}(1)$, where we consider two faces to be adjacent if their
intersection is non-empty. More commonly, proper combinatorial balls with
respect to edge-distance in a graph with vertex set $V$ are defined as
$\mathcal{B}_{k}(x)=\\{y\in V:d(x,y)\leq k\\}$. Then viewing the
$\mathcal{B}_{k}(x)$ as a structure on the dual graph of an animal, the
definitions of $A_{p,q}(k)$ and $\mathcal{B}_{k}(x)$ coincide when $q=3$,
since every face in the $k$-th layer is necessarily glued along an edge to a
face of $A_{p,q}(k-1)$. However, when $q\geq 4$ there will always be new faces
only glued to the previous layer at a vertex, and $\mathcal{B}_{k}(x)$ will
correspond to a sub-animal of $A_{p,q}(k)$.

In [13], Keller and Peyerimhoff compute the perimeter of these combinatorial
balls $\mathcal{B}_{k}(x)$. These values are then used to find the exponential
growth of the graph, defined as,

$\mu=\limsup_{k\to\infty}\frac{\log\text{vol}(\mathcal{B}_{k}(x))}{k}.$

They obtain $\mu=\tau+\sqrt{\tau^{2}-1}$ for the $\\{p,q\\}$-tessellation,
where $\tau=q-\frac{2}{p-2}$. This value is related to our $t=(p-2)(q-2)-2$ by
$\tau=\frac{t}{p-2}+2$. Moreover, Theorem 1.3 can be stated in terms of the
combinatorial curvature at a vertex of a $\\{p,q\\}$-tessellation, given by
$\kappa=1-\frac{q}{2}+\frac{q}{p}=\frac{2-t}{2p}$.

In [22], Mertens and Moore find recursive formulas for the number of vertices
and tiles on the sequence $A_{p,q}(k)$ in order to sample a certain type of
random hyperbolic $\\{p,q\\}$-animals that allows them to give computational
estimates of hyperbolic percolation thresholds on $\\{p,q\\}$-tessellations.

Instead of relying on these independent and related works, we give a complete
proof of Theorem 1.3 to keep the discussion self-contained. In addition, our
analysis is aimed at a more detailed description of the perimeter structure of
$A_{p,q}(k)$, which we use to compute the graph parameters of all extremal
$n$-tile $\\{p,q\\}$-animals.

After proving Theorem 1.3, we construct and analyze a sequence of spiral
animals with $n$ tiles, of which the complete $k$-layered animals are a
subsequence. These $\\{p,q\\}$-spirals are denoted by $S_{p,q}(n)$ and are
constructed in roughly the following way: find the maximum $k$ such that
$\check{n}(k)\leq n$, then attach $n-\check{n}(k)$ adjacent tiles in one
direction along the boundary of $A_{p,q}(k)$, saturating perimeter vertices
one a time along the way. The definition of the sequence $S_{p,q}(n)$ is made
more precise in Definition 4.1 (see Figure 2).

Before discussing the spirals in more detail, we pause here for a minute to
point out the subtleties in the deluge of notation and bookkeeping we employ
to keep track of all the parameters we are interested in. In particular, the
same set of graph parameters are discussed in three distinct settings, and we
use variations on the notation $v$, $e$, and $n$ for each. First, we have the
parameters of $A_{p,q}(k)$, which use the adorned letters presented in Theorem
1.3 with the layer value as the input. For the spiral $S_{p,q}(n)$ we use
unadorned letters and the tile number as the input, e.g.,
$v(n)=v(S_{p,q}(n)),e(n)=e(S_{p,q}(n))$, etc. For a $\\{p,q\\}$-animal $A$ or
it’s underlying planar graph, we use unadorned notation and input the animal’s
name, e.g., $v(A)$, $e(A)$, etc.

For the spiral $S_{p,q}(n)$, we compute its parameters in terms of the
sequence of vertex degrees on the perimeter of the previous layer of the
spiral. To accomplish this, it is useful to label the vertices on the
perimeter of $A_{p,q}(k)$ by $x_{k,i}$, and to denote by $d_{k,i}$ the degree
of $x_{k,i}$. The sequences $d_{k,i}$ are computed recursively at the end of
Section 3.

Figure 2. $S_{p,q}(n)$ for $n=37$ and $\\{p,q\\}=\\{4,5\\}$. $A_{4,5}(2)$ is
shown in dark-gray, the light-gray tiles are those necessary to complete
$S_{4,5}(37)$. The growth of the spiral is depicted by the dotted lines. Big-
dot points mark the beginning (in the counter-clockwise direction) of the
perimeter vertices on each layer; these are denoted by $x_{k,1}$. The number
of perimeter vertices of $A_{4,5}(2)$ that are interior vertices of
$S_{4,5}(37)$ is $m=9$; these vertices are marked by a dashed circle. See [20]
for our interactive applets to explore spiral animals and their graph
parameters.

######  Theorem 1.5.

Fix $\\{p,q\\}$ such that $(p-2)(q-2)\geq 4$. Let $S_{p,q}(n)$ be the
$\\{p,q\\}$-spiral with $n$ tiles, and let $k$ be such that $\check{n}(k)\leq
n<\check{n}(k+1)$. Let $m$ count the number of perimeter vertices of
$A_{p,q}(k)$ that are saturated in $S_{p,q}(n)$. Then,

$\displaystyle e(n)$ $\displaystyle=(p-1)(n-\check{n}(k))+\check{e}(k)-m,$
$\displaystyle v(n)$ $\displaystyle=(p-2)(n-\check{n}(k))+\check{v}(k)-m.$
$\displaystyle e_{1}(n)$
$\displaystyle=(p-2)(n-\check{n}(k))+\check{e}_{1}(k)-2m,$

Furthermore, $m$ can be computed as follows: If $n-\check{n}(k)\leq
q-d_{k,1}$, then $m=0$. And otherwise $m$ takes the unique value $\geq 1$ such
that

(1.6) $\displaystyle\sum_{i=1}^{m}(q-d_{k,i})\leq
n-\check{n}(k)-1<\sum_{i=1}^{m+1}(q-d_{k,i}).$

The next theorem states that the spirals in fact attain extremal values in the
graph parameters listed above. It is natural to imagine that this should be
the case, as the spiral configuration intuitively has the effect of wrapping
up as many vertices and edges in the interior as possible, where they can be
shared by the most tiles. Thus, interior parameters are maximized while
perimeter and overall counts are minimized.

######  Theorem 1.7.

Fix $\\{p,q\\}$ such that $(p-2)(q-2)\geq 4$, and let $A$ be a
$\\{p,q\\}$-animal with $n$ tiles. Then $e_{2}(A)$ and $v_{int}(A)$ are
maximized, and $e_{1}(A)$, $e(A)$, and $v(A)$ are minimized when
$A=S_{p,q}(n)$.

Spiral-like animals have also been used by Buchholz and de Launey [6] for
exploring the extremal combinatorial problem of edge-minimization for families
of $\\{p,q\\}$-animals that do not tessellate the Euclidean plane. They use
spiral-like arrangements to obtain asymptotic results for extremal values on
the number of internal edges. In that setting, it remains open as to whether
these spiral-like arrangements are actually extremal, that is, if they attain
and provide the exact minimal optimal values for the number of internal edges.

Theorem 1.7 shows that the minimum perimeter attainable by a
$\\{p,q\\}$-animal with $n$ tiles, which we denote by $\mathcal{P}_{p,q}(n)$,
is equal to $e_{1}(n)$. Plugging the Euclidean $\\{p,q\\}$ values into Theorem
1.5, we recover Harary and Harborth’s formulas for extremal values of animals
on regular tessellations of the Euclidean plane [7].

######  Corollary 1.8.

For $\\{p,q\\}=\\{3,6\\}$, $\\{4,4\\}$, and $\\{6,3\\}$, we have

$\displaystyle\mathcal{P}_{3,6}(n)$
$\displaystyle=2\left\lceil\frac{1}{2}(n+\sqrt{6n})\right\rceil-n,$
$\displaystyle\mathcal{P}_{4,4}(n)$ $\displaystyle=2\left\lceil
2\sqrt{n}\right\rceil,$ $\displaystyle\mathcal{P}_{6,3}(n)$
$\displaystyle=2\left\lceil\sqrt{12n-3}\right\rceil.$

While the Euclidean cases immediately yield closed formulas, in the hyperbolic
case it remains open to find a closed formula for $\mathcal{P}_{p,q}$ in terms
of $n$.

Finally, we address the problem of enumerating extremal $n$-tile animals for a
fixed $n$, exhibiting several sequences which give unique extremal animals up
to isometries. The question of counting extremal animals was first posed by
Harary and Harborth in [7]. In the $\\{4,4\\}$ case [15], Kurz proved that
squares and pronic rectangles, i.e. polyominoes with $l^{2}$ tiles and
rectangles with $l(l+1)$ tiles for $l\geq 1$, respectively, are unique
extremal animals up to isometries. Here, we find sequences of
$\\{p,q\\}$-animals which generalize this result for all $\\{p,q\\}$ pairs in
Theorems 6.3 and 6.4.

The rest of the paper is structured as follows: In Section 2, we set up
notation and discuss graph theoretic formulae we will need later on. In
Section 3, we analyze the layered animals $A_{p,q}(k)$, we deduce formulas for
their parameters to prove Theorem 1.3, and we write the substitution rules
necessary to construct their perimeter sequence of vertex degrees $d_{k,i}$.
We conclude Section 3 with detailed examples that highlight the difference
between the Euclidean and hyperbolic cases. Then, in Section 4, we prove
Theorem 1.5 by finding algebraic expressions for the parameters of
$S_{p,q}(n)$ in terms of the sequences $d_{k,i}$. In Section 5, we provide the
proof of Theorem 1.7 which states that spirals are indeed extremal. In Section
6, we prove Theorems 6.3 and 6.4 regarding unique extremal animals. And
finally, in Section 7, we state open problems and give concluding remarks.

##  2\. Definitions and Preliminary Results

To begin, we restrict ourselves to animals with no holes, where a hole is
defined to be a finite connected component of the complement. We then extend
results on extremality to animals with holes as the last piece in proving
Theorem 1.7.

Consider a $\\{p,q\\}$-animal $A$ with no holes. The edges and vertices of the
$p$-gons of $A$ define a planar graph in which all vertices have degree at
least 2 and at most $q$, and its bounded faces are all regular $p$-gons. Here,
and throughout this paper we use the term faces only to refer to the _bounded_
faces of a planar graph. So the number of tiles of $A$ is equal to the number
of faces of its underlying planar graph, which we also refer to simply as $A$,
conflating the notation for convenience.

There is also a dual graph $G^{\prime}$ associated with any planar graph $G$,
constructed by placing a vertex at each face and connecting two vertices if
and only if their corresponding faces share an edge. For an animal $A$, the
dual graph $A^{\prime}$ may not be an animal, as some edges may not be
contained in any faces. Thus we define a larger class of planar graphs to work
in, which contains all graphs defined by animals with no holes.

######  Definition 2.1.

We call $G$ a $\\{p,q\\}$-graph if $G$ is a planar graph in which each vertex
of $G$ has degree at most $q$, and each face of $G$ has exactly $p$ edges.

Then a $\\{p,q\\}$-animal with no holes is necessarily a $\\{p,q\\}$-graph.
However, not every $\\{p,q\\}$-graph is the graph of an animal or even a
subgraph of the regular $\\{p,q\\}$-tessellation. For instance, we can build a
rooted $\\{p,q\\}$-tree starting with a single vertex, the root $R$, which has
$q$ adjacent vertices. Then we give each of $R$’s neighbors $q-1$ distinct
additional neighbors, and then each of those new vertices get $q-1$ distinct
additional neighbors, and so on. After more than $p/2$ iterations of this,
such a graph can no longer live in the $\\{p,q\\}$-tessellation, as these
strings starting from $R$ would necessarily form $p$-gons.

For the rest of this paper, we always assume that $(p-2)(q-2)\geq 4$ for the
pair $\\{p,q\\}$. We denote the total number of vertices, edges and faces of a
fixed graph $G$ in the same manner as for a $\\{p,q\\}$-animal, using $v(G)$,
$e(G)$ and $n(G)$, respectively. Furthermore, we partition the vertices and
edges by the number of incident edges and faces, respectively:

$\displaystyle v_{i}(G)$ $\displaystyle=\\#\text{ vertices of degree }i,\text{
for }1\leq i\leq q-1,$ $\displaystyle v_{q}(G)$ $\displaystyle=\\#\text{
vertices of degree $q$ incident to only $q-1$ faces,}$ $\displaystyle
v_{int}(G)$ $\displaystyle=\\#\text{ interior vertices, i.e., vertices of
degree $q$ incident to $q$ faces,}$ $\displaystyle e_{i}(G)$
$\displaystyle=\\#\text{ edges incident to $i$ faces, for }i=0,1,2.$

All non-interior vertices are called _perimeter_ vertices, and these are
partitioned by the $v_{i}$ according to their degrees.

When a fixed $G$ is understood, we write simply $v$, $e$, $n$, etc, and for
its dual graph $G^{\prime}$ we write $v^{\prime}$, $e^{\prime}$, $n^{\prime}$,
etc. It is easily seen that when $G$ is a $\\{p,q\\}$-graph, $p$ and $q$
switch roles for $G^{\prime}$, which is a $\\{q,p\\}$-graph. In general,
$v^{\prime}$, $e^{\prime}$ and $n^{\prime}$ can be counted directly by various
parameters of $G$. We know by definition that $v^{\prime}=n$; the edges of
$G^{\prime}$ correspond to edges of $G$ which are incident to two faces of
$G$, and hence $e^{\prime}=e_{2}$; and a face of $G^{\prime}$ corresponds to
an interior vertex of $G$, so $n^{\prime}=v_{int}$. We further partition the
edges of the dual graph and count its connected components:

$\displaystyle e_{2,i}(G)$ $\displaystyle=\\#\text{ edges in $G^{\prime}$
incident to $i$ faces, for }i=0,1,2,$ $\displaystyle c^{\prime}(G)$
$\displaystyle=\\#\text{ connected components of $G^{\prime}$.}$

Figure 3. A $\\{5,5\\}$-animal and its dual. Its parameters are $n=13$,
$e=50$, $e_{1}=36$, $e_{2}=14$, $v=38$, $v_{int}=2$, $e_{2,0}=5$, $e_{2,1}=8$
and $e_{2,2}=2$. Any resemblance to a real animal is pure coincidence; no
animals were harmed for this research.

When $G$ is an animal, $c^{\prime}$ is always 1 by definition. But here we
will obtain more general bounds for all $\\{p,q\\}$-graphs. Using Euler’s
formula for $G^{\prime}$, and also counting its edges with respect to incident
faces, we have that:

$\displaystyle n-e_{2}+v_{int}$ $\displaystyle=c^{\prime},$ $\displaystyle
q\cdot v_{int}$ $\displaystyle=e_{2,1}+2e_{2,2}=e_{2}-e_{2,0}+e_{2,2}.$

Combining these equations to eliminate $v_{int}$ yields

(2.2) $\displaystyle e_{2}=\frac{q(n-c^{\prime})-e_{2,0}+e_{2,2}}{q-1}.$

This formula will allow us to use induction to prove that $e_{2}(G)\leq
e_{2}(S_{p,q}(n))$ for any $\\{p,q\\}$-graph with exactly $n$ faces by
translating the inequality to the dual graphs.

We will also need the following lemma which asserts that the number of tiles
decreases when we perform the dual operation. Observe that if a
$\\{p,q\\}$-graph is a _tree_ , that is a connected graph with no faces, then
$v_{int}=0$ and the dual graph of that component is the empty graph. Thus, it
is sufficient to only consider components with faces.

######  Lemma 2.3.

Let $G$ be a $\\{p,q\\}$-graph with $q\geq 4$ such that every connected
component has at least one face. Then $v_{int}\leq n-1$. Moreover, if $q=3$
then $v_{int}\leq 2n-2$, and if $q\geq 6$ then $v_{int}<\frac{n}{2}$.

###### Proof.

The Handshake Lemma and Euler’s formula for $G$ are:

$\displaystyle q\cdot v_{int}+\sum_{i=1}^{q}i\cdot v_{i}$ $\displaystyle=2e,$
$\displaystyle v-e+n$ $\displaystyle=c.$

Using these equations to eliminate $e$ we obtain:

$(q-2)v_{int}+\sum_{i=1}^{q}(i-2)\cdot v_{i}=2n-2c.$

The sum of $(i-2)\cdot v_{i}$ can be negative if $v_{1}>0$, and to avoid this
we iteratively prune all degree 1 vertices, one at a time, until there are
none left. Cycles in a graph cannot be deleted via this process, therefore
since each component is assumed to have at least one face, the resulting graph
has the same number of faces, interior vertices, and connected components as
$G$. Let $\bar{v}_{i}$ denote the corresponding parameters in the reduced
graph, with $\bar{v}_{1}=0$. Then

$(q-2)v_{int}\leq(q-2)v_{int}+\sum_{i=2}^{q}(i-2)\cdot\bar{v}_{i}=2n-2c\leq
2n-2.$

This gives the desired bounds, choosing the appropriate $q$ in each case. ∎

##  3\. Complete $k$-layered $\\{p,q\\}$-animals

In this section, we define and study the main properties of the complete
$k$-layered $\\{p,q\\}$-animals $A_{p,q}(k)$. Recall from Definition 1.2 that
$A_{p,q}(1)$ is the regular $p$-gon, and then $A_{p,q}(k)$ is constructed
inductively by attaching all allowable tiles to the perimeter of
$A_{p,q}(k-1)$. The graph parameters of $A_{p,q}(k)$ are denoted by
$\check{v}(k)$, $\check{e}(k)$, $\check{n}(k)$, etc.

As each new layer is added, these parameters can be tracked by characterizing
the geometry of how individual tiles are attached. When adding a tile $T$ to
an animal $A$, we use the notation $\deg_{A}(T)$ to denote the number of edges
$T$ shares with $A$. This is, in fact, the degree of the vertex representing
$T$ in the dual graph of $A\cup T$. More informally, we describe a tile being
added to a given animal as being _$\epsilon$ -glued_ if
$\deg_{A}(T)=\epsilon$. In constructing $A_{p,q}(k)$ from $A_{p,q}(k-1)$, we
consider each tile individually and examine $\deg_{A_{p,q}(k-1)}(T)$ for every
tile $T$ in the $k$-th layer. We will use this parameter to classify a layer’s
perimeter vertices by degree, and then find recursive formulas counting the
number of each degree in a layer.

One key observation is that the intersection of a tile in the $k$-th layer
with $A_{p,q}(k-1)$ is a connected path, which may be only a single vertex, in
which case the tile is _0-glued_. Then a given perimeter edge gets covered
with a single tile, and we must consider if that tile can cover any adjacent
edges on the perimeter as well. For instance, a tile that is 2-glued will
completely cover one shared vertex with $A_{p,q}(k-1)$, which is possible if
and only if that vertex already has degree $q$ in $A_{p,q}(k-1)$. Otherwise
0-glued tiles must be filled in next to a 1-glued tile until the degree of the
common perimeter vertex is $q$ (see Figure 5).

Figure 4. Here we depict $A_{p,q}(k)$ for $\\{p,q\\}=\\{3,7\\}$ and $k=3$.
Big-dot points mark the beginning of the perimeter vertices on each layer,
these are denoted by $x_{k,1}$. The degree of each perimeter vertex of
$A_{3,7}(3)$ is written next to it; this is the sequence $d_{3,i}$, starting
at $x_{3,1}$ in the counter-clockwise direction. See Figure 1 for the cases
$\\{4,4\\}$ and $\\{4,5\\}$.

.

######  Remark 3.1.

If $p=3$, all perimeter vertices of $A_{p,q}(k)$ are degree 3 or 4, for $k\geq
2$. If $p\geq 4$, all perimeter vertices of $A_{p,q}(k)$ are degree 2 or 3.

######  Remark 3.2.

If $q=3$, then all tiles in $A_{p,q}(k)$ are either 1-glued or 2-glued to
$A_{p,q}(k-1)$, with one 2-glued tile for every vertex of degree 3 in
$A_{p,q}(k-1)$. If $q\geq 4$, every tile is either 0-glued or 1-glued.

Inherent in the proof of the recursions in Proposition 3.3 below is an
inductive argument confirming these remarks, which are inextricably linked
with each other. For instance, assuming Remark 3.1, if $q\geq 4$ there can
never be perimeter vertices of degree $q$, because degree 4 vertices only
exist for $p=3$, and $p=3$ requires $q\geq 6$. Consequently, there cannot be
$\epsilon$-glued tiles for $\epsilon\geq 2$ when $q\geq 4$. Conversely, if
$p=3$, then $q\geq 6$ and every tile is 0-glued or 1-glued, and the ensuing
geometry can be used to show that all perimeter vertices have degree 3 or 4.

######  Proposition 3.3.

Recall that perimeter vertices of $A_{p,q}(k)$ are counted by
$\check{v}_{i}(k)$ according to their degree $i$. So $\check{v}_{2}(k)$,
$\check{v}_{3}(k)$ and $\check{v}_{4}(k)$ are the number of perimeter vertices
of $A_{p,q}(k)$ of degree 2, 3, and 4, respectively. Then, for $p=3$ and
$k\geq 3$,

$\displaystyle\check{v}_{3}(k)$
$\displaystyle=(q-5)\check{v}_{3}(k-1)+(q-6)\check{v}_{4}(k-1),$
$\displaystyle\check{v}_{4}(k)$
$\displaystyle=\check{v}_{3}(k-1)+\check{v}_{4}(k-1).$

For $p\geq 4$ and $k\geq 2$,

$\displaystyle\check{v}_{2}(k)$
$\displaystyle=\left((p-3)(q-2)-1\right)\check{v}_{2}(k-1)+\left((p-3)(q-3)-1\right)\check{v}_{3}(k-1),$
$\displaystyle\check{v}_{3}(k)$
$\displaystyle=(q-2)\check{v}_{2}(k-1)+(q-3)\check{v}_{3}(k-1).$

###### Proof.

Suppose $p=3$. Then $q\geq 6$ and a perimeter vertex $x$ of $A_{p,q}(k-1)$ of
degree $d=3,4$ belongs to $d-1$ tiles of $A_{p,q}(k-1)$. To construct
$A_{p,q}(k)$, we attach $q-d+1$ tiles to $x$. To avoid overlap, we associate
to $x$ only the first $q-d$ tiles in the counterclockwise direction. Note that
$q-d\geq 2$. The first tile is always 1-glued to $A_{p,q}(k-1)$, while the
remaining $q-d-1\geq 1$ are 0-glued at a common vertex. So the first tile
contributes one perimeter vertex of $A_{p,q}(k)$ of degree 4, and the next
$q-d-2$ tiles each contribute one vertex of degree 3. The last tile associated
to $x$ does not add to this count, as it shares one perimeter vertex with the
previous tile associated to $x$, and the other with a 1-glued tile whose
perimeter vertex is counted by the next vertex of $A_{p,q}(k)$. In summary,
all perimeter vertices of $A_{p,q}(k-1)$ of degree 3 contribute in total to
$(q-5)\check{v}_{3}(k-1)$ perimeter vertices of $A_{p,q}(k)$ of degree 3 and
$\check{v}_{3}(k-1)$ vertices of degree 4. Similarly, perimeter vertices of
$A_{p,q}(k-1)$ of degree 4 contributes to $(q-6)\check{v}_{4}(k-1)$ perimeter
vertices of $A_{p,q}(k)$ of degree 3 and $\check{v}_{4}(k-1)$ vertices of
degree 4. By adding these two contributions, we arrive at the recurrence
formulas for $p=3$.

Figure 5. Left: When $p=3$, each vertex of degree $d=3$ or $4$ in
$A_{p,q}(k-1)$, contributes to a vertex of degree 4 in $A_{p,q}(k)$ and
$q-d-2$ vertices of degree $=3$. Right: When $p\geq 4$, each vertex of degree
$3$ in $A_{p,q}(k-1)$, contributes to $q-3$ vertices of degree $=3$ in
$A_{p,q}(k)$ and $(q-3)(p-3)-1$ vertices of degree $=2$.

The case for $p\geq 4$ is analogous. Each perimeter vertex of degree $d$ in
$A_{p,q}(k-1)$ has $q-d+1$ tiles of $A_{p,q}(k)$ attached to it, but we
consider only the first $q-d$ tiles, to avoid overlapping. Note that the first
tile is always 1-glued to $A_{p,q}(k-1)$, and the rest are 0-glued to a common
vertex. So the first has $p-2$ perimeter vertices, and the rest have $p-1$,
but we subtract the last one in a counterclockwise direction from each to
avoid overlap. Then each of the $q-d$ tiles contributes one perimeter vertex
of $A_{p,q}(k)$ of degree 3, which is incident to the adjacent tile in the
clockwise direction, and $p-3$ vertices of degree 2, with the exception of the
first tile which has one vertex of degree 3 and $p-4$ of degree 2. In summary,
a perimeter vertex of $A_{p,q}(k-1)$ of degree $d$ contributes $q-d$ vertices
of degree 3 to $A_{p,q}(k)$ and $(q-d)(p-3)-1$ vertices of degree 2. This
gives the recurrence relations for $p\geq 4$. ∎

######  Lemma 3.4.

Let $t=(p-2)(q-2)-2$ and $\alpha=\frac{t+\sqrt{t^{2}-4}}{2}$,
$\beta=\frac{t-\sqrt{t^{2}-4}}{2}$. The solution to the recurrence relations
of Proposition 3.3 are:

  1. (1)

When $t=2$ we have the Euclidean cases:

$\displaystyle\text{For }\\{p,q\\}=$ $\displaystyle\,\\{3,6\\},\,k\geq 2,$
$\displaystyle\text{For }\\{p,q\\}=$ $\displaystyle\,\\{4,4\\},$
$\displaystyle\text{For }\\{p,q\\}=$ $\displaystyle\,\\{6,3\\},$
$\displaystyle\check{v}_{3}(k)$ $\displaystyle=6,$
$\displaystyle\check{v}_{2}(k)$ $\displaystyle=4,$
$\displaystyle\check{v}_{2}(k)$ $\displaystyle=6k,$
$\displaystyle\check{v}_{4}(k)$ $\displaystyle=3+6(k-2),$
$\displaystyle\check{v}_{3}(k)$ $\displaystyle=8(k-1),$
$\displaystyle\check{v}_{3}(k)$ $\displaystyle=6(k-1).$

  2. (2)

For $p=3$, $q>6$ and $k\geq 2$,

$\displaystyle\check{v}_{3}(k)$
$\displaystyle=\frac{3}{\alpha-\beta}\left((\alpha-1)(q-3-\beta)\alpha^{k-2}+(1-\beta)(q-3-\alpha)\beta^{k-2}\right),$
$\displaystyle\check{v}_{4}(k)$
$\displaystyle=\frac{3}{\alpha-\beta}\left((q-3-\beta)\alpha^{k-2}-(q-3-\alpha)\beta^{k-2}\right).$

  3. (3)

For $p\geq 4$ and $(p-2)(q-2)>4,$

$\displaystyle\check{v}_{2}(k)$
$\displaystyle=\frac{p}{\alpha-\beta}\left(-(q-3-\alpha)\alpha^{k-1}+(q-3-\beta)\beta^{k-1}\right),$
$\displaystyle\check{v}_{3}(k)$
$\displaystyle=\frac{p}{\alpha-\beta}\left((q-2)\alpha^{k-1}-(q-2)\beta^{k-1}\right).$

###### Proof.

This is the result of solving a linear system of $2\times 2$ recurrence
relations; the associated matrix in both cases has determinant 1 and trace
$t=(p-2)(q-2)-2$. The characteristic polynomial is then $x^{2}-tx+1$, and its
roots are $\alpha$ and $\beta$.

When $t=2$, we have $\alpha=\beta=1$, and the growth is linear. When $t>2$, we
get exponential growth in terms of $\alpha$ and $\beta$. The initial
conditions are $\check{v}_{3}(2)=3(q-4)$, $\check{v}_{4}(2)=3$ for $p=3$, and
$\check{v}_{2}(1)=p$, $\check{v}_{3}(1)=0$ for $p\geq 4$. The diagonalization
matrix is

$\displaystyle M=\begin{pmatrix}1-\alpha&1-\beta\\\ -1&-1\end{pmatrix}\text{
for }p=3,\text{ or
}M=\begin{pmatrix}\frac{q-3-\alpha}{q-2}&\frac{q-3-\beta}{q-2}\\\
-1&-1\end{pmatrix}\text{ for }p\geq 4.$

The $k$th element of the sequences can be computed from

$\displaystyle\begin{pmatrix}\check{v}_{3}(k)\\\
\check{v}_{4}(k)\end{pmatrix}=M\begin{pmatrix}\alpha^{k-2}&0\\\
0&\beta^{k-2}\end{pmatrix}M^{-1}\begin{pmatrix}\check{v}_{3}(2)\\\
\check{v}_{4}(2)\end{pmatrix},\text{ for $p=3$,}$

$\displaystyle\begin{pmatrix}\check{v}_{2}(k)\\\
\check{v}_{3}(k)\end{pmatrix}=M\begin{pmatrix}\alpha^{k-1}&0\\\
0&\beta^{k-1}\end{pmatrix}M^{-1}\begin{pmatrix}\check{v}_{2}(1)\\\
\check{v}_{3}(1)\end{pmatrix},\text{ for }p\geq 4.$

From these we obtain the desired expressions. ∎

###### Proof of Theorem 1.3.

Firstly, we work the case $p\geq 4$. The vertices of $A_{p,q}(k)$ consists of
its perimeter plus those of $A_{p,q}(k-1)$, that is,
$\check{v}(k)=\check{v}(k-1)+\check{v}_{2}(k)+\check{v}_{3}(k)$, then

$\check{v}(k)=\sum_{j=1}^{k}\check{v}_{2}(j)+\check{v}_{3}(j).$

As the perimeter of $A_{p,q}(k)$ is a cycle, then $\check{e}_{1}(k)$ is equal
to the number of vertices on the perimeter. That is,
$\check{e}_{1}(k)=\check{v}_{2}(k)+\check{v}_{3}(k)$. Next, $\check{e}_{2}(k)$
consists of the interior and perimeter edges of $A_{p,q}(k-1)$, plus the
interior edges of $A_{p,q}(k)\setminus A_{p,q}(k-1)$, which also correspond to
the edges that connect perimeter vertices of $A_{p,q}(k-1)$ and $A_{p,q}(k)$.
The latter are precisely $q-d$ for each vertex of degree $d$ in the perimeter
of $A_{p,q}(k-1)$. Then
$e_{2}(k)=\check{e}_{2}(k-1)+\check{e}_{1}(k-1)+(q-2)\check{v}_{2}(k-1)+(q-3)\check{v}_{3}(k-1)=\check{e}_{2}(k-1)+(q-1)\check{v}_{2}(k-1)+(q-2)\check{v}_{3}(k-1)$.
Now, recalling that $\check{e}_{2}(1)=0$, we get,

$\check{e}_{2}(k)=(q-1)\sum_{j=1}^{k-1}\check{v}_{2}(j)+(q-2)\sum_{j=1}^{k-1}\check{v}_{3}(j).$

Finally, $\check{e}(k)=\check{e}_{1}(k)+\check{e}_{2}(k)$ and
$\check{n}(k)=1-\check{v}(k)+\check{e}(k)$. All the previous, together with
the expressions for $\check{v}_{2}(k)$ and $\check{v}_{3}(k)$, give us the
formulas for Theorem 1.3. We just have to notice that $\beta=\alpha^{-1}$,
$\alpha+\beta=t$, and $\alpha-\beta=\sqrt{t^{2}-4}$.

The case for $p=3$ is analogous. The only subtle difference is that

$\check{e}_{2}(k)=(q-2)\sum_{j=1}^{k-1}\check{v}_{3}(j)+(q-3)\sum_{j=1}^{k-1}\check{v}_{4}(j).$

∎

Here, we collect the formulas for $A_{p,q}(k)$ in the hyperbolic case,
$(p-2)(q-2)>4$.

(3.5)
$\begin{split}\check{n}(k)&=1+\frac{p(q-2)}{(\alpha-1)\sqrt{t^{2}-4}}\left(\alpha^{k}+\frac{1}{\alpha^{k-1}}-\alpha-1\right)\\\
\check{v}(k)&=\frac{p}{t-2}\left(\alpha^{k}+\frac{1}{\alpha^{k}}-2\right)\\\
\check{e}(k)&=\frac{p}{(\alpha-1)\sqrt{t^{2}-4}}\left((\alpha+q-1)\alpha^{k}+\frac{\alpha
q-\alpha+1}{\alpha^{k}}-q(\alpha+1)\right)\\\
\check{e}_{1}(k)&=\frac{p(\alpha+1)}{\sqrt{t^{2}-4}}\left(\alpha^{k-1}-\frac{1}{\alpha^{k}}\right)\\\
\check{e}_{2}(k)&=\frac{p}{(\alpha-1)\sqrt{t^{2}-4}}\left((\alpha
q-\alpha+1)\alpha^{k-1}+\frac{q-1+\alpha}{\alpha^{k-1}}-q(\alpha+1)\right)\\\
\check{v}_{int}(k)&=\frac{p}{t-2}\left(\alpha^{k-1}+\frac{1}{\alpha^{k-1}}-2\right)\end{split}$

Now, we establish how to construct the sequences $d_{k,i}$. To begin with, we
order the vertices on the boundary of $A_{p,q}(k)$, labeling them $x_{k,i}$
for $1\leq i\leq\check{e}_{1}(k)$.

######  Definition 3.6.

For $A_{p,q}(1)$, label the vertices $x_{1,1},x_{1,2},\dots,x_{1,p}$ in the
counter-clockwise direction. For $k\geq 2$, suppose that we have labelled the
perimeter vertices of $A_{p,q}(k-1)$, and let $T$ be the tile of $A_{p,q}(k)$
attached to both $x_{k-1,1}$ and $x_{k-1,\check{e}_{1}(k-1)}$, the first and
last vertices of $A_{p,q}(k-1)$. Define $x_{k,1}$ to be the vertex of $T$
adjacent to $x_{k-1,\check{e}_{1}(k-1)}$, and different from $x_{k-1,1}$.
Then, the perimeter vertices of $A_{p,q}(k)$ are labelled in the counter-
clockwise direction starting at $x_{k,1}$. See Figures 2 and 4.

Now, recall from the proof of Proposition 3.3 that each vertex in $A_{p,q}(k)$
generates vertices on the next layer according to its degree. Let $d_{k}$
denote the sequence $\\{d_{k,i}\\}$. We can compute the sequence $d_{k+1}$
from $d_{k}$ in the following manner. See the ensuing figures.

Firstly, $d_{1}$ is the sequence $2,2,\dots,2$ containing $p$ elements. Then,
$d_{k}$ is constructed from $d_{k-1}$ by replacing the $i$th element
$d_{k-1,i}$ with the string of the degrees of the perimeter vertices of
$A_{p,q}(k)$ associated to $x_{k-1,i}$. More precisely: If $p\geq 4$ and
$q\geq 4$, $d_{k-1,i}$ is replaced by

$\underbrace{\underbrace{3,2,\dots,2}_{p-3},\underbrace{3,2,\dots,2}_{p-2},\dots,\underbrace{3,2,\dots,2}_{p-2}}_{q-d_{k-1,i}\text{
groups of }3,2,\dots,2}.$

If $p=3$, and $q\geq 6$, $d_{k-1,i}$ is replaced by

$\underbrace{4,3,\dots,3}_{q-d_{k-1,i}-1}.$

Finally, if $q=3$, and $p\geq 6$, $d_{k-1,i}=2$ is replaced by

$\underbrace{3,2,\dots,2}_{p-3}\text{ or }\underbrace{3,2,\dots,2}_{p-4}$

depending whether $d_{k-1,i}=2$ is preceded by a 2 or a 3, respectively. On
the other hand, $d_{k-1,i}=3$ is simply erased.

######  Example 3.7.

Here, we compute the sequences $d_{k}$ for the Euclidean cases and some
hyperbolic ones. As expected, from Lemma 3.4, we will encounter linear growth
in the former and exponential in the latter. In [20], we also provide an
applet to explore these examples and their numerical properties.

  * A)

For $\\{p,q\\}=\\{3,6\\}$, the substitution rules are: $4\to 4$; $3\to 4,3$;
and $2\to 4,3,3$. The first sequences are

$\displaystyle d_{1}$ $\displaystyle=2,2,2$ $\displaystyle d_{2}$
$\displaystyle=4,3,3,\dots$ $\displaystyle(\text{3 times})$ $\displaystyle
d_{3}$ $\displaystyle=4,4,3,4,3,\dots$ $\displaystyle(\text{3 times})$
$\displaystyle d_{4}$ $\displaystyle=4,4,4,3,4,4,3,\dots$
$\displaystyle(\text{3 times})$

It is easy to see that, for $k\geq 3$, $d_{k}$ consists of the sequence
$\underbrace{4,4\dots,4,3}_{k}\underbrace{4,4\dots,4,3}_{k-1}$, repeated 3
times.

Figure 6. Graphic representation of the substitution rules for
$\\{p,q\\}=\\{3,7\\}$. From $A_{3,7}(1)$ to $A_{3,7}(2)$ we apply $2\to
4,3,3,3$. From $A_{3,7}(2)$ to $A_{3,7}(3)$ we apply $3\to 4,3,3$ and $4\to
4,3$. We observe that in this case we only have vertices of degree two in
$A_{3,7}(1)$ but then all the vertices of $A_{3,7}(k)$ for $k>1$ will have
degree $3$ or $4$.

  * B)

For $\\{p,q\\}=\\{3,7\\}$, the substitution rules are: $4\to 4,3$; $3\to
4,3,3$; and $2\to 4,3,3,3$. The first sequences are

$\displaystyle d_{1}$ $\displaystyle=2,2,2$ $\displaystyle d_{2}$
$\displaystyle=4,3,3,3,\dots$ $\displaystyle(\text{3 times})$ $\displaystyle
d_{3}$ $\displaystyle=4,3,4,3,3,4,3,3,4,3,3,\dots$ $\displaystyle(\text{3
times})$ $\displaystyle d_{4}$
$\displaystyle=4,3,4,3,3,4,3,4,3,3,4,3,3,4,3,4,3,3,4,3,3,4,3,4,3,3,4,3,3,\dots$
$\displaystyle(\text{3 times})$

  * C)

For $\\{p,q\\}=\\{4,4\\}$, the substitution rules are: $3\to 3$, and $2\to
3,3,2$. The first sequences are

$\displaystyle d_{1}$ $\displaystyle=2,2,2,2$ $\displaystyle d_{2}$
$\displaystyle=3,3,2,\dots$ $\displaystyle(\text{4 times})$ $\displaystyle
d_{3}$ $\displaystyle=3,3,3,3,2,\dots$ $\displaystyle(\text{4 times})$
$\displaystyle d_{4}$ $\displaystyle=3,3,3,3,3,3,2,\dots$
$\displaystyle(\text{4 times})$

It is easy to see that, for $k\geq 2$, $d_{k}$ consists of the sequence
$\underbrace{3,3\dots,3,2}_{2k-1}$, repeated 4 times.

Figure 7. Graphic representation of the substitution rules for
$\\{p,q\\}=\\{4,5\\}$. From $A_{4,5}(1)$ to $A_{4,5}(2)$ we apply $2\to
3,3,2,3,2$; the associated tiles are shaded in light gray. We alternate the
symbols $\blacktriangle$ and $\bullet$ to emphasize the substitution rules for
each perimeter vertex of $A_{4,5}(2)$.

  * D)

For $\\{p,q\\}=\\{4,5\\}$, the substitution rules are: $3\to 3,3,2$, and $2\to
3,3,2,3,2$. The first sequences are

$\displaystyle d_{1}$ $\displaystyle=2,2,2,2$ $\displaystyle d_{2}$
$\displaystyle=3,3,2,3,2,\dots$ $\displaystyle(\text{4 times})$ $\displaystyle
d_{3}$ $\displaystyle=3,3,2,3,3,2,3,3,2,3,2,3,3,2,3,3,2,3,2,\dots$
$\displaystyle(\text{4 times})$

  * E)

For $\\{p,q\\}=\\{6,3\\}$, the substitution rules are: $3$ is erased; if a $2$
is preceded by a $3$, then $2\to 3,2$; and if a $2$ is preceded by a $2$, then
$2\to 3,2,2$. The first sequences are

$\displaystyle d_{1}$ $\displaystyle=2,2,2,2,2,2$ $\displaystyle d_{2}$
$\displaystyle=3,2,2,\dots$ $\displaystyle(\text{6 times})$ $\displaystyle
d_{3}$ $\displaystyle=3,2,2,3,2,\dots$ $\displaystyle(\text{6 times})$
$\displaystyle d_{4}$ $\displaystyle=3,2,3,2,2,3,2,2,\dots$
$\displaystyle(\text{6 times})$

It is easy to see that, for $k\geq 2$, $d_{k}$ consists of the sequence
$3,2,\underbrace{3,2,2,3,2,2,\dots,3,2,2}_{3,2,2\text{ repeated }k-2\text{
times}}$, repeated 6 times.

Figure 8. Graphic representation of the substitution rules for
$\\{p,q\\}=\\{7,3\\}$. From $A_{7,3}(2)$ to $A_{7,3}(3)$, the 3 is erased
(represented by $\times$), and $2\to 3,2,2,2$. We alternate the symbols
$\blacktriangle$ and $\bullet$ to emphasize the substitution rules for each
vertex.

  * F)

For $\\{p,q\\}=\\{7,3\\}$, the substitution rules are: $3$ is erased; if a $2$
is preceded by a $3$, then $2\to 3,2,2$; and if a $2$ is preceded by a $2$,
then $2\to 3,2,2,2$. The first sequences are

$\displaystyle d_{1}$ $\displaystyle=2,2,2,2,2,2,2$ $\displaystyle d_{2}$
$\displaystyle=3,2,2,2,\dots$ $\displaystyle(\text{7 times})$ $\displaystyle
d_{3}$ $\displaystyle=3,2,2,3,2,2,2,3,2,2,2\dots$ $\displaystyle(\text{7
times})$ $\displaystyle d_{4}$
$\displaystyle=3,2,2,3,2,2,2,3,2,2,3,2,2,2,3,2,2,2,3,2,2,3,2,2,2,3,2,2,2,\dots$
$\displaystyle(\text{7 times})$

##  4\. $\\{p,q\\}$-spiral animals

In this section, we turn our attention to $\\{p,q\\}$-spiral animals, counting
their graph parameters, and proving Theorem 1.5.

The $\\{p,q\\}$-spiral with $n$ tiles will be denoted by $S_{p,q}(n)$. Recall
that we refer to its graph parameters as $e(n),v(n),e_{1}(n)$, etc. The
following procedure for constructing $S_{p,q}(n)$ gives the spiral in the
counter-clockwise direction, as seen in Figure 2.

######  Definition 4.1.

Let $n$ be a positive integer. Then $S_{p,q}(n)$ is constructed by adding
tiles $T_{1},T_{2},\ldots,T_{n}$ one at a time such that $T_{n}$ is the unique
tile added to $S_{p,q}(n-1)$ to obtain $S_{p,q}(n)$. If $n=\check{n}(k)$, then
$S_{p,q}(n)=A_{p,q}(k)$. Otherwise, for $\check{n}(k)<n<\check{n}(k+1)$, first
$T_{\check{n}(k)+1}$ is attached to $A_{p,q}(k)$ by gluing it along the edge
$\\{x_{k,1},x_{k,\check{e}_{1}(k)}\\}$. Then subsequent tiles $T_{i}$ are
added by gluing along the perimeter edge of $T_{i-1}$ which contains
$x_{k,1}$, until $x_{k,1}$ is saturated. Next, we move on to the vertex
$x_{k,2}$, and we repeat this process until $n-\check{n}(k)$ tiles have been
added to $A_{p,q}(k)$.

For the rest of this section, we always assume that
$\check{n}(k)<n\leq\check{n}(k+1)$, and thus $T_{n}$ is a tile being added in
the $(k+1)$-th layer. Similar to $A_{p,q}(k)$, we use the gluing parameter of
each subsequent tile to chart the jumps in the sequences $e_{1}(n)$ and
$e_{2}(n)$. Here, $T_{n}$ is added to $S_{p,q}(n-1)$, and so we say $T_{n}$ is
$\epsilon$-glued if $\deg_{S_{p,q}(n-1)}(T_{n})=\epsilon$, with $\epsilon\geq
1$ since $T_{n}$ always shares an edge with $T_{n-1}$.

######  Remark 4.2.

If $T_{n}$ is $\epsilon$-glued to $S_{p,q}(n-1)$, then

$\displaystyle e_{1}(n)-e_{1}(n-1)$ $\displaystyle=p-2\epsilon,$
$\displaystyle e_{2}(n)-e_{2}(n-1)$ $\displaystyle=\epsilon.$

This is a simple observation, as when $T_{n}$ is $\epsilon$-glued it adds
$p-\epsilon$ perimeter edges while covering $\epsilon$ edges of
$S_{p,q}(n-1)$, and each covered edge is added to the count for $e_{2}$.

With $T_{n}$ in the $(k+1)$-th layer, note that $\deg_{S_{p,q}(n-1)}(T_{n})$
is also easily determined from $\deg_{A_{p,q}(k)}(T_{n})$, differing by either
0, 1, or 2 additional edges. The first tile $T_{\check{n}(k)+1}$ has no
additional shared edges with other tiles in the $(k+1)$-th layer, and is
1-glued for $q\geq 4$ and 2-glued for $q=3$ (the latter for $k\geq 2$).
Meanwhile, the last tile $T_{\check{n}(k+1)}$ has two additional shared edges;
one with $T_{\check{n}(k+1)-1}$ and one with the first tile in this layer,
$T_{\check{n}(k)+1}$. Thus, it is 2-glued for $q\geq 4$ or 3-glued for $q=3$.
For any other value of $n$, $T_{n}$ only shares one additional edge with
$T_{n-1}$, and so $\deg_{S_{p,q}(n-1)}(T_{n})=\deg_{A_{p,q}(k)}(T_{n})+1$.
Combining this with the analysis in Proposition 3.3 and Remarks 3.1 and 3.2,
we can then determine the exact values of these jumps.

######  Lemma 4.3.

When $q>3$ and for $n>1$,

$\displaystyle e_{1}(n)-e_{1}(n-1)=p-2\text{ or }p-4,$ $\displaystyle
e_{2}(n)-e_{2}(n-1)=1\text{ or 2, respectively}.$

When $q=3$ and for $n>2$,

$\displaystyle e_{1}(n)-e_{1}(n-1)=p-4\text{ or }p-6,$ $\displaystyle
e_{2}(n)-e_{2}(n-1)=2\text{ or 3, respectively}.$

######  Corollary 4.4.

For $n\geq 1$ and $l\geq 1$, we have the bounds

$\displaystyle e_{2}(n+l)-e_{2}(n)\leq 2l\text{ when }q>3,$ $\displaystyle
e_{2}(n+l)-e_{2}(n)\leq 3l\text{ when }q=3.$

###### Proof of Theorem 1.5.

Recall that $e_{1}(n)$ is the number of perimeter edges of $S_{p,q}(n)$, and
$m$ is the number of perimeter vertices of $A_{p,q}(k)$ which are saturated in
$S_{p,q}(n)$.

When $T_{n}$ is $\epsilon$-glued, it saturates $\epsilon-1$ perimeter vertices
of $A_{p,q}(k)$. So an $\epsilon$-glued tile increments $m$ by $\epsilon-1$,
and $e_{1}$ by $p-2\epsilon=(p-2)-2$(increment of $m$). Then, for any $q$, we
get

$e_{1}(n)=(p-2)(n-\check{n}(k))+\check{e}_{1}(k)-2m,$

which gives the expression in Theorem 1.5. Similarly, we have

$\displaystyle e_{2}(n)$ $\displaystyle=\check{e}_{2}(k)+n-\check{n}(k)+m,$
$\displaystyle e(n)$ $\displaystyle=(p-1)(n-\check{n}(k))+\check{e}(k)-m,$
$\displaystyle v(n)$ $\displaystyle=(p-2)(n-\check{n}(k))+\check{v}(k)-m.$

Now, we compute $m$ with the help of the sequence $d_{k,i}$. The vertex
$x_{k,1}$ has degree $d_{k,1}$ in $A_{p,q}(k)$, hence it needs $q-d_{k,i}+1$
tiles to become saturated. So, if $n-\check{n}(k)\leq q-d_{k,1}$ then $m=0$.
Now, for $i>1$, the vertex $x_{k,i}$ has degree $d_{k,i}$ in $A_{p,q}(k)$, but
in the spiral there is already a tile attached to both $x_{k,i-1}$ and
$x_{k,i}$; so $x_{k,i}$ needs $q-d_{k,i}$ tiles to become saturated. This
analysis, together with the fact that $n-\check{n}(k)$ must be between the
number of tiles needed to saturate $m$ vertices and the number of tiles needed
to saturate $m+1$ vertices, gives us the inequality,

$1+\sum_{i=1}^{m}(q-d_{k,i})\leq
n-\check{n}(k)<1+\sum_{i=1}^{m+1}(q-d_{k,i}).$

∎

We now turn our attention to the properties of the dual graph of $S_{p,q}(n)$.
Recall that $n^{\prime}$ is the number of faces in the dual graph, and we use
$T_{n^{\prime}}$ and $T_{n^{\prime}+1}$ to denote the $n^{\prime}$-th and
$(n^{\prime}+1)$-th tiles of the dual $\\{q,p\\}$-spiral. Additionally, recall
that $e_{2,i}$ is the number of edges that are incident to $i$ faces in the
dual graph, with $e_{2,0}$ tracking how far off $S^{\prime}_{p,q}(n)$ is from
being exactly a $\\{q,p\\}$-spiral.

######  Lemma 4.5.

The dual graph of $S_{p,q}(n)$ consists of the $\\{q,p\\}$-spiral animal
$S_{q,p}(n^{\prime})$ with a possibly trivial path of $e_{2,0}$-edges
attached. Moreover, if $T_{n^{\prime}+1}$ is $\epsilon$-glued to
$S_{q,p}(n^{\prime})$, then $e_{2,0}(n)\leq q-2-\epsilon$.

###### Proof.

Recall that dual faces, i.e., tiles of the dual animal, are in 1-to-1
correspondence with interior vertices of the original. Then by Definition 4.1,
we want to show that if $x_{k,i}$ is an interior vertex that corresponds to
tile $T_{n^{\prime}}$ in the dual, then vertex $x_{k,i+1}$ (or $x_{k+1,1}$
when $i=\check{e}_{1}(k)$) corresponds to the tile $T_{n^{\prime}+1}$ in the
dual. To briefly avoid confusion caused by the index, we write $x_{*}$ to
denote whichever of $x_{k,i+1}$ or $x_{k+1,1}$ is the next vertex.

For $n\leq q$, this is trivially true, and covering the vertex $x_{1,1}$ of
$T_{1}$ gives $S^{\prime}_{p,q}(q)=S_{q,p}(1)$. For larger $n$, this follows
from Definition 4.1, since tiles are added in the same direction as the
increments in the vertex labels. For instance, it is clear that the tiles
represented by $x_{k,i}$ and $x_{*}$ will be adjacent, and the tile $T$ of
$A_{p,q}(k)$ containing the edge $\\{x_{k,i},x_{*}\\}$ corresponds to the next
open perimeter vertex in the dual, to which $T_{n^{\prime}+1}$ is being glued.
Furthermore, when $q>3$, 1-glued tiles correspond to adding a path of
$e_{2,0}$-edges in the dual. This path gets closed at the next 2-glued tile,
which saturates $x_{*}$ and completes $T_{n^{\prime}+1}$.

The bound follows from counting the extant edges of $T_{n^{\prime}+1}$ in the
dual. There are $\epsilon$ edges already present in $S_{q,p}(n^{\prime})$,
where it is going to be attached. The vertex representing the 2-glued tile in
the original $\\{p,q\\}$-spiral completes the tile $T_{n^{\prime}+1}$, adding
two edges simultaneously. So these $\epsilon+2$ edges cannot be in the path
tracing out the $q$-gon $T_{n^{\prime}+1}$. ∎

##  5\. Proof of Theorem 1.7

We now work towards proving Theorem 1.7 and the extremality of the graph
properties of $S_{p,q}(n)$. Recall that an animal $A$ with $n$ tiles is said
to be extremal if $e_{2}(A)$ and $v_{int}(A)$ are maximal, and $e(A),e_{1}(A)$
or $v(A)$ are all minimal in the set of animals with $n$ tiles.

First, we show the maximality of $e_{2}(n)$ within the class of
$\\{p,q\\}$-graphs with $n$ faces. This requires the following lemma, which
asserts that if this holds for the dual structure, then it can be lifted to
the original graph.

######  Lemma 5.1.

Let $G$ be a $\\{p,q\\}$-graph with $n$ faces and $v_{int}$ interior vertices.
If $e_{2}\left(G^{\prime}\right)\leq
e_{2}\left(S_{q,p}\left(v_{int}\right)\right)$, then $e_{2}(G)\leq e_{2}(n)$.

###### Proof.

Recall that $e_{2,2}(G)=e_{2}\left(G^{\prime}\right)$, which by assumption is
at most $e_{2}\left(S_{q,p}\left(v_{int}\right)\right)$. Then, we can plug
this into Equation (2.2),

$\displaystyle e_{2}(G)$
$\displaystyle=\frac{q\left(n-c^{\prime}\right)-e_{2,0}(G)+e_{2,2}(G)}{q-1},$
$\displaystyle\leq\frac{q\left(n-c^{\prime}\right)+e_{2,2}(G)}{q-1}$
$\displaystyle\leq\frac{q\left(n-c^{\prime}\right)+e_{2}\left(S_{q,p}\left(v_{int}\right)\right)}{q-1}.$

To avoid a cacophony of indices and parentheses, we abbreviate our notation
when referring to the dual $\\{q,p\\}$-spiral and write
$\tilde{e}_{2}(i)=e_{2}\left(S_{q,p}(i)\right)$. Then applying Euler’s
identity for $G^{\prime}$ to replace $v_{int}$, we have

$e_{2}(G)\leq\frac{q\left(n-c^{\prime}\right)+\tilde{e}_{2}\left(v_{int}\right)}{q-1}=\frac{q\left(n-c^{\prime}\right)+\tilde{e}_{2}\left(e_{2}(G)-n+c^{\prime}\right)}{q-1}.$

We can reduce this to the case $c^{\prime}=1$ by using Corollary 4.4 to obtain

$\tilde{e}_{2}\left(e_{2}(G)-n+c^{\prime}\right)=\tilde{e}_{2}\left(e_{2}(G)-n+1+c^{\prime}-1\right)\leq\tilde{e}_{2}\left(e_{2}(G)-n+1\right)+3\left(c^{\prime}-1\right).$

And similarly adding and subtracting 1 to $n-c^{\prime}$ in the first term, we
get

(5.2)
$\begin{split}e_{2}(G)&\leq\frac{q\left(n-c^{\prime}\right)+\tilde{e}_{2}\left(e_{2}(G)-n+c^{\prime}\right)}{q-1},\\\
&\leq\frac{q(n-1)-q\left(c^{\prime}-1\right)+\tilde{e}_{2}\left(e_{2}(G)-n+1\right)+3\left(c^{\prime}-1\right)}{q-1},\\\
&\leq\frac{q(n-1)+\tilde{e}_{2}\left(e_{2}(G)-n+1\right)}{q-1}.\end{split}$

The last inequality follows from the fact that $q\geq 3$, so the coefficient
of $\left(c^{\prime}-1\right)$ is at most 0.

Now we define the sequence

$g_{n}(j)=\tilde{e}_{2}(j-n+1)-(q-1)j+q(n-1),$

noting that a simple rearrangement of the inequality in Equation (5.2) yields
$g_{n}(e_{2}(G))\geq 0$. To prove $e_{2}(G)\leq e_{2}(n)$, we will show that
$g_{n}$ is non-increasing, and $j=e_{2}(n)$ is the last value where it is non-
negative.

That $g_{n}$ is non-increasing is primarily a consequence of Corollary 4.4
applied to the $\\{q,p\\}$-spiral $S_{q,p}(j-n+1)$. Using $\delta$ as the
multiplicative factor, which here depends on $p$ instead of $q$,

$\displaystyle g_{n}(j+1)$
$\displaystyle=\tilde{e}_{2}(j-n+1+1)-(q-1)(j+1)+q(n-1),$
$\displaystyle\leq\tilde{e}_{2}(j-n+1)+\delta-(q-1)j-(q-1)+q(n-1),$
$\displaystyle=g_{n}(j)-q+\delta+1.$

Recall that $\delta=2$ if $p>3$ and $\delta=3$ if $p=3$. In the first case,
$q\geq 3$, and in the second $q\geq 6$, so we always get $g_{n}(j+1)\leq
g_{n}(j)$.

Then $g_{n}(e_{2}(n))=g_{n}\left(e_{2}\left(S_{p,q}(n)\right)\right)\geq 0$
follows from $g_{n}\left(e_{2}(G)\right)\geq 0$ for any $\\{p,q\\}$-graph $G$
with $n$ faces, and it only remains to show that
$g_{n}\left(e_{2}(n)+1\right)<0$. Recall that the dual of $S_{p,q}(n)$ is
connected by definition, and is a $\\{q,p\\}$-spiral with $n^{\prime}$ faces
and possibly some additional edges. Hence $c^{\prime}=1$, and by Euler’s
formula the number of faces in the dual is $n^{\prime}=1-n+e_{2}(n)$, with
$\tilde{e}\left(n^{\prime}\right)=e_{2}(n)$. Now, we can apply Remark 4.2 to
$\tilde{e}_{2}\left(1-n+e_{2}(n)+1\right)=\tilde{e}_{2}\left(n^{\prime}+1\right)$.
For $\epsilon$ the gluing parameter of the tile $T_{n^{\prime}+1}$ in the
$\\{q,p\\}$-spiral, we get that

$\displaystyle g_{n}\left(e_{2}(n)+1\right)$
$\displaystyle=\tilde{e}_{2}\left(n^{\prime}+1\right)-(q-1)\left(e_{2}(n)+1\right)+q(n-1),$
$\displaystyle=\tilde{e}_{2}\left(n^{\prime}\right)+\epsilon-(q-1)e_{2}(n)-(q-1)+q(n-1).$

And Equation (2.2) for $G=S_{p,q}(n)$ yields that

$\displaystyle e_{2,0}(n)$ $\displaystyle=e_{2,2}(n)-(q-1)e_{2}(n)+q(n-1),$
$\displaystyle=\tilde{e}_{2}\left(n^{\prime}\right)-(q-1)e_{2}(n)+q(n-1).$

So we have

$\displaystyle g_{n}\left(e_{2}(n)+1\right)=e_{2,0}(n)+\epsilon-(q-1).$

Finally, Lemma 4.5 tell us that $e_{2,0}(n)\leq q-2-\epsilon$, and hence
$g_{n}\left(e_{2}(n)+1\right)\leq-1$. Therefore, since
$g_{n}\left(e_{2}(G)\right)\geq 0$, it must be that $e_{2}(G)\leq e_{2}(n)$. ∎

We use induction and the bounds from Lemma 2.3 to show that this lifting can
always be done, and $e_{2}(n)$ is in fact always maximal in the class of
$\\{p,q\\}$-graphs.

######  Lemma 5.3.

Fix a pair $\\{p,q\\}$ and $n\geq 0$. If $G$ is a $\\{p,q\\}$-graph with $n$
faces, then $e_{2}(G)\leq e_{2}(n)$.

###### Proof.

We proceed by induction, leveraging the dual structure and Lemma 4.5. Let
$\mathcal{I}(p,q,n)$ be the statement:

“If $G$ is a $\\{p,q\\}$-graph with exactly $n$ faces, then $e_{2}(G)\leq
e_{2}(n)$.”

Our initial base case will be that $\mathcal{I}(p,q,n)$ holds for all $p,q$
and $n$ such that $n\leq q$. When $n<q$, there cannot be any interior
vertices. So the dual graph of $G$ is either a tree, a disjoint union of
trees, or the empty graph on $n$ vertices, and $e_{2}(G)=e(G^{\prime})\leq
n-1=e_{2}(n)$. Similarly, when $n=q$, the optimal value is obtained when the
dual graph is a $q$-cycle, then $e_{2}(G)\leq q=e_{2}(q)$.

Next, we observe that Lemma 5.1 asserts that $\mathcal{I}(p,q,n)$ follows from
$\mathcal{I}(q,p,v_{int})$, where we slightly abuse notation and allow
$v_{int}$ to represent any viable value for $v_{int}$ given a
$\\{p,q\\}$-graph with $n$ faces. To make this more rigorous, we combine this
with the bounds in Lemma 2.3 for $v_{int}$ in terms of $n$ to get the
following three facts:

  * (1)

For $p,q\geq 4$, $\mathcal{I}(p,q,n)$ follows from the set
$\\{\mathcal{I}(q,p,i):i\leq n-1\\}$.

  * (2)

For $p=3$, $\mathcal{I}(3,q,n)$ follows from the set
$\\{\mathcal{I}(q,3,i):i\leq n/2\\}$.

  * (3)

For $q=3$, $\mathcal{I}(p,3,n)$ follows from the set
$\\{\mathcal{I}(3,p,i):i\leq 2n-2\\}$.

First, we show $\mathcal{I}(p,q,n)$ holds for all $n$ in the case that both
$p,q\geq 4$. Fix $q\geq 4$. Then, for any $p>q$ and any $q<n\leq p$, we have
that $v_{int}<p$ by Lemma 2.3. Hence $\mathcal{I}(q,p,v_{int})$ is satisfied
by the base cases, and for any pair $p,q\geq 4$, we conclude
$\mathcal{I}(p,q,n)$ holds for all $n\leq\max(p,q)$.

Now suppose that for all pairs $p,q\geq 4$, the statement $\mathcal{I}(p,q,i)$
holds for all $i\leq\max(p,q)+j$ for some fixed integer $j\geq 0$. Then, for
any fixed $p$ and $q$, let $n=\max(p,q)+j+1$. Thus $\mathcal{I}(p,q,n)$
follows by statement (1) and the induction assumption, and applying this to
each ordered pair $(p,q)$ allows us to increment $j$ by 1 in the assumption.
Therefore $\mathcal{I}(p,q,n)$ holds for all $n$ and all $p,q\geq 4$.

Next, fix one parameter at 3, and denote the other by $r\geq 6$. Then
$\mathcal{I}(r,3,n)$ follows from $\mathcal{I}(3,r,v_{int})$ if we set
$2n-2\leq r$, and hence $n\leq(r+2)/2$. Conversely, for $\mathcal{I}(3,r,n)$
we need up to $\mathcal{I}(r,3,n/2)$. By the previous statement for the $q=3$
case, we know $\mathcal{I}(r,3,n/2)$ holds if $n/2\leq(r+2)/2\Rightarrow n\leq
r+2$. Hence for every $r\geq 6$, we have that $\mathcal{I}(r,3,n)$ holds for
$n\leq(r+2)/2$, and $\mathcal{I}(3,r,n)$ holds for $n\leq r+2$. Using these as
the base cases, we zipper them together to perform the induction.

Fix any $r\geq 6$, and suppose that for a fixed $j\geq 0$,
$\mathcal{I}(r,3,i)$ holds for all $i\leq(r+2)/2+j$, and additionally
$\mathcal{I}(3,r,i)$ holds for all $i\leq r+2+2j$. Let $n=(r+2)/2+j+1$. Then a
graph considered in $\mathcal{I}(r,3,n)$ has $v_{int}\leq 2n-2=r+2+2j$.
Similarly, for $n=r+2+2j+1$, a graph considered in $\mathcal{I}(3,r,n)$ has
$v_{int}\leq n/2=(r+2)/2+j+1/2$. For $n=r+2+2j+2$, the bound is $v_{int}\leq
n/2=(r+2)/2+j+1$. Hence, adding 1 to $n$ in the $q=3$ case is covered by the
assumption in the $p=3$ case, and adding either 1 or 2 in the $p=3$ case is
covered by the assumption in the $q=3$ case. Thus, we can increment $j$ by 1
for every $r\geq 6$ in both cases, and by induction $\mathcal{I}(r,3,n)$ and
$\mathcal{I}(3,r,n)$ hold for all $r\geq 6$ and all $n\geq 0$.

∎

The maximality of $e_{2}(n)$ can immediately be churned into the full litany
of extremal properties of spiral animals in the class of $\\{p,q\\}$-graphs.
As a corollary, we obtain a proof of the statement of Theorem 1.7 in the
particular case for animals with no holes.

######  Corollary 5.4.

Let $A$ be a $\\{p,q\\}$-animal with $n$ tiles and no holes. Then
$e_{2}(A)\leq e_{2}(n)$, $v_{int}(A)\leq v_{int}(n)$, $e_{1}(A)\geq e_{1}(n)$,
$e(A)\geq e(n)$, and $v(A)\geq v(n)$.

###### Proof.

Any $\\{p,q\\}$-animal $A$ with no holes can be regarded as a
$\\{p,q\\}$-graph. Lemma 5.3 implies that $e_{2}(A)\leq e_{2}(n)$, and the
remaining inequalities are obtained from the relations between the graph
parameters: $e=e_{1}+e_{2}=p\cdot n-e_{2}$; $e_{1}=p\cdot n-2e_{2}$;
$v_{int}=1+e_{2}-n$; and $v=1-n+e$. ∎

To prove Theorem 1.7, it remains to show that this corollary also holds for
animals with holes. We will use induction on the number of holes to complete
the proof, but first we require the following lemma stating that the number of
interior edges in $S_{p,q}(n)$ plus the total number of edges in $S_{p,q}(l)$
is at least the number of interior edges in $S_{p,q}(n+l)$.

######  Lemma 5.5.

For any fixed $n>1$ and fixed $l\geq 1$,

$e_{2}(n)+e(l)\geq e_{2}(n+l).$

###### Proof.

Note that $e(l)=p\cdot l-e_{2}(l)$. By Corollary 4.4 along with the base case
$e_{2}(1)=0$, we know that $e_{2}(l)\leq\delta\cdot l$, where $\delta=2$ for
$q>3$, and $\delta=3$ for $q=3$. Now consider the case $p\geq 4$, in which
$p\geq 2\delta$ (if $\delta=2$ then $q>3$ and $p\geq 4$, if $\delta=3$ then
$q=3$ and $p\geq 6$). Then we have that

$\displaystyle e_{2}(n)+e(l)$ $\displaystyle=e_{2}(n)+p\cdot l-e_{2}(l),$
$\displaystyle\geq e_{2}(n)+p\cdot l-\delta\cdot l,$ $\displaystyle\geq
e_{2}(n)+\delta\cdot l,$ $\displaystyle\geq e_{2}(n+l).$

The last inequality is again Corollary 4.4, this time applied to $S_{p,q}(n)$.

When $p=3$, we need a sharper analysis. Note that $p=3$ forces $q\geq 6$, and
so all tiles are either 1- or 2-glued. Therefore, the increments of the
sequence $e_{2}(l)-l$ are either 0 or 1, respectively. Furthermore, up to a
small offset due to the initial value being $e_{2}(1)-1=-1$, this sequence
counts the number tiles that are 2-glued. Recall that these 2-glued tiles are
exactly those which completely surround a perimeter vertex, forcing it to the
interior. Since for $p=3$ the perimeter vertices of $A_{p,q}(k)$ have degree
$\leq 4$, we need at least $q-3$ tiles to surround a perimeter vertex, the
first and last of which are always 2-glued. Thus the increments of 1 are
separated by at least $q-5$ increments of 0. On the other hand, for fixed $n$
the sequence $e_{2}(n)+2l-e_{2}(n+l)$ counts the number of 1-glued tiles added
when constructing $S_{p,q}(n+l)$ starting from $S_{p,q}(n)$. The increments of
this sequence are again 0 or 1, but now the increments by 0 are the 2-glued
tiles. Since 1-glued tiles are added at a consistent ratio of at least $q-5$
to 1, and $e_{2}(l)-l$ actually starts at -1, we conclude that

$\displaystyle e_{2}(n)+2l-e_{2}(n+l)$ $\displaystyle\geq e_{2}(l)-l,$
$\displaystyle=3l-e(l)-l.$

The equality here follows from the edge partition formula $e(l)=3l-e_{2}(l)$,
and then a simple rearrangement of the inequality gives the desired result.

∎

###### Proof of Theorem 1.7.

Suppose that $e_{2}(n)$ is maximal in the class of $\\{p,q\\}$-animals with
$h$ holes, and let $A$ be a $\\{p,q\\}$-animal with $n$ tiles and $h+1$ holes.
Let $H$ be one of the holes of $A$, where $H$ itself is regarded as a
$\\{p,q\\}$-animal, and let $l$ be the number of tiles of $H$. Denote by
$\bar{A}$ the $\\{p,q\\}$-animal obtained by filling in $H$ in $A$. This is an
animal with $n+l$ tiles and $h$ holes, so by the induction hypothesis
$e_{2}(n+l)\geq e_{2}\left(\bar{A}\right)$. Observe that
$e_{2}\left(\bar{A}\right)=e_{2}(A)+e(H)$, and thus Lemma 5.5 implies that

$\displaystyle e_{2}(n)+e(l)$ $\displaystyle\geq e_{2}(n+l),$
$\displaystyle\geq e_{2}\left(\bar{A}\right),$ $\displaystyle=e_{2}(A)+e(H),$
$\displaystyle\geq e_{2}(A)+e(l).$

Note that $e(H)\geq e(l)$, since $H$ is a $\\{p,q\\}$-animal with no holes.
Therefore, by induction we conclude that $e_{2}(n)\geq e_{2}(A)$ for any
$\\{p,q\\}$-animal $A$ with $n$ tiles. Then the other inequalities follow, as
they did for Corollary 5.4, due to the equalities $e=p\cdot n-e_{2}$,
$e_{1}=p\cdot n-2e_{2}$, $v_{int}=1+e_{2}-n$, and $v=1-n+e$. ∎

Given the extremality of all the pertinent graph parameters, we now briefly
show how to derive the equations from [7] for the Euclidean cases.

###### Proof of Corollary 1.8.

For the case $\\{p,q\\}=\\{3,6\\}$ we know $\check{n}(k)=6k^{2}-6k+1$ and,
from Example 3.7, the sequence $d_{k}$ is equal to
$\underbrace{4,4\dots,4,3}_{k}\underbrace{4,4\dots,4,3}_{k-1}$, repeated 3
times, for $k\geq 3$. From these values we deduce the following formula for
$e_{1}(n)$ valid for $k\geq 3$.

$\displaystyle e_{1}(n)=\begin{cases}6k-3+\bmod(n-1,2)&\text{if $0\leq
n-\check{n}(k)\leq 1$}\\\ 6k-2+\bmod(n,2)&\text{if $2\leq n-\check{n}(k)\leq
2k-1$}\\\ 6k-1+\bmod(n-1,2)&\text{if $2k\leq n-\check{n}(k)\leq 4k-1$}\\\
6k+\bmod(n,2)&\text{if $4k\leq n-\check{n}(k)\leq 6k$}\\\
6k+1+\bmod(n-1,2)&\text{if $6k+1\leq n-\check{n}(k)\leq 8k-1$}\\\
6k+2+\bmod(n,2)&\text{if $8k\leq n-\check{n}(k)\leq 10k$}\\\
6k+3+\bmod(n-1,2)&\text{if $10k+1\leq n-\check{n}(k)\leq 12k-1$}\\\
\end{cases}$

Then it is a straightforward computation to check that it can be written as

$\displaystyle e_{1}(n)$
$\displaystyle=2\left\lceil\frac{1}{2}(n+\sqrt{6n})\right\rceil-n$

A similar analysis holds for the cases $\\{p,q\\}=\\{4,4\\}$ and $\\{6,3\\}$.
∎

##  6\. Enumeration of extremal $\\{p,q\\}$-animals

In 2008 [15], Kurz enumerated polyominoes, i.e. $\\{4,4\\}$-animals, that
attain minimum perimeter for any fixed number of tiles. Moreover, he proved
that for all $l\geq 1$ there exists a unique polyomino with $l^{2}$ tiles
which is extremal, and also a unique polyomino with $l(l+1)$ tiles. The former
are the square shape polyominoes with side length $l$, and the latter are
pronic rectangles with side lengths $l$ and $l+1$. In the general $\\{p,q\\}$
setting, we find that the sequence $A_{p,q}(k)$ corresponds precisely to
squares with odd side lengths, and we define three more sequences
corresponding to even squares and the two types of pronic rectangles
distinguished by the parity of the shorter side. We are then able to
generalize Kurz’s result and show that each of these sequences yields unique
extremal $\\{p,q\\}$-animals for any $p$ and $q$.

First we define the sequence $B_{p,q}(k)$ analogously to $A_{p,q}(k)$; but
start with $B_{p,q}(1)=x_{0}$, a single vertex. Then $B_{p,q}(2)$ is the set
of $q$ tiles incident to $x_{0}$, and $B_{p,q}(3)$ is the set of all tiles
incident to the perimeter of $B_{p,q}(2)$, and so on. These form another
distinct subsequence of spirals that are related to the $A_{p,q}(k)$ through
the dual graph. Observe that the $B_{p,q}(k)$ sequence corresponds directly to
the square shaped polyominoes with even side length in the $\\{4,4\\}$ case.

######  Remark 6.1.

The dual of $A_{p,q}(k)$ is $B_{q,p}(k)$, and thus $B_{p,q}(k)=S_{p,q}(n)$ for
$n=v_{int}\left(A_{q,p}(k)\right)$. Similarly, the dual of $B_{p,q}(k)$ is
$A_{q,p}(k-1)$.

We will use the duality of these two structures to build an inductive proof of
their uniqueness, but first, we require a short proposition establishing a
condition under which, up to isometries, an animal and its dual graph are in
1-to-1 correspondence.

######  Proposition 6.2.

Let $A$ be a $\\{p,q\\}$-animal such that $e_{2,0}(A)=0$. If $M$ is a
$\\{p,q\\}$-animal with $M^{\prime}=A^{\prime}$, then $M=A$.

###### Proof.

The faces of $A^{\prime}$ always represent a fixed set of vertices in the
$\\{p,q\\}$-lattice which are saturated in $A$. By definition, a vertex is
saturated if and only if all $q$ incident tiles are present in $A$. But if
$e_{2,0}(A)=0$, then every vertex of $A^{\prime}$ is incident to a face of
$A^{\prime}$, and hence every tile of $A$ is incident to a saturated vertex of
$A$. So a tile is in $A$ if and only if it is incident to a saturated vertex.
But then $M^{\prime}=A^{\prime}$ implies that also $e_{2,0}(M)=0$, so by the
same reasoning a tile is in $M$ if and only if it is incident to a saturated
vertex. Therefore, since $A$ and $M$ have the same set of saturated vertices,
it must be that $M=A$. ∎

######  Theorem 6.3.

For any $k\geq 1$, $A_{p,q}(k)$ is the unique extremal $\\{p,q\\}$-animal with
$\check{n}(k)$ tiles. Similarly, the same is true for $B_{p,q}(k)$ for $k\geq
2$, where the number of tiles is computed from $S_{p,q}(n)$ for
$n=v_{int}\left(A_{q,p}(k)\right)$.

###### Proof of Theorem 6.3.

The statement is trivially true for $A_{p,q}(1)$ for all $p$ and $q$. The
induction will proceed by zippering the two sequences, with $B_{p,q}(k)$
following from $A_{q,p}(k-1)$ and then $A_{p,q}(k)$ following from
$B_{q,p}(k)$.

Suppose that $A_{p,q}(k-1)$ is a unique extremal animal for all $p$ and $q$.
Then for any fixed $p$ and $q$, let $B$ be a $\\{p,q\\}$-animal with
$n(B)=n\left(B_{p,q}(k)\right)$ and perimeter
$e_{1}(B)=e_{1}\left(B_{p,q}(k)\right)$. By the relations in the proof of
Corollary 5.4, we then have that $B$ has the same number of interior edges and
interior vertices as $B_{p,q}(k)$. Thus $B^{\prime}$ has the same number of
edges and faces as the dual of $B_{p,q}(k)$, which is $A_{q,p}(k-1)$.

Since $A_{q,p}(k-1)$ is itself a spiral, it’s number of edges
$e_{2,2}\left(B_{p,q}(k)\right)$ is maximal for its number of faces. Hence
$e_{2,2}(B)\leq e_{2,2}\left(B_{p,q}(k)\right)$. Then by Equation (2.2) with
$c^{\prime}=1$ in both cases, it must be that $e_{2,0}(B)=0$, and thus
$e_{2,2}(A)=e_{2,2}\left(B_{p,q}(k)\right)$. So the dual of $B$ has the same
number of faces, edges, and interior edges as $A_{q,p}(k-1)$. And by our
inductive assumption $A_{q,p}(k-1)$ is the unique animal with these
parameters, and it must be that $B^{\prime}=A_{q,p}(k-1)$. Hence, since
$e_{2,0}=0$, by Proposition 6.2 we can lift this equality to get
$B=B_{p,q}(k)$, which is therefore the unique extremal animal with
$n=v_{int}\left(A_{q,p}(k)\right)$ tiles.

The exact same argument suffices to show that the uniqueness of $A_{p,q}(k)$
follows from knowing uniqueness for $B_{q,p}(k)$. Therefore, by induction we
have uniqueness of $A_{p,q}(k)$ for all $k\geq 1$, and for $B_{p,q}(k)$ for
all $k\geq 2$. ∎

To extend now the pronic case, we define two more sequences in a similar
fashion to the $A_{p,q}(k)$ and $B_{p,q}(k)$. Let $C_{p,q}(1)$ be the
$\\{p,q\\}$-animal which has two tiles glued along a single adjoining edge,
and let $D_{p,q}(1)$ be the $\\{p,q\\}$-graph which is simply a single edge
connecting two vertices. Then the sequences $C_{p,q}(k)$ and $D_{p,q}(k)$ are
defined analogously, with all possible tiles incident to the perimeter added
in each subsequent step.

Figure 9. Left: $B_{4,5}(3)$ and its dual $A_{5,4}(2)$. Center: $C_{3,7}(2)$
and its dual $D_{7,3}(2)$. Right: $C_{7,3}(2)$ and its dual $C_{3,7}(2)$

######  Theorem 6.4.

For any $k\geq 1$, $C_{p,q}(k)$ is a unique extremal animal. Similarly, for
any $k\geq 2$, $D_{p,q}(k)$ is a unique extremal animal.

###### Proof.

Note that as in the previous case, both of these sequences are subsequences of
the spiral $S_{p,q}(n)$, and thus are extremal. Furthermore, the dual of
$C_{p,q}(k)$ is $D_{q,p}(k)$, and the dual of $D_{p,q}(k)$ is $C_{q,p}(k-1)$.
It is clear that up to isometries that there is only one $\\{p,q\\}$-animal on
two tiles, and hence $C_{p,q}(1)$ is unique. The proof then follows by the
same inductive argument as in the proof of Theorem 6.3. ∎

Figure 10. Free extremal $\\{4,5\\}$-animals with 9 tiles.

As shown in Figure 10, it is not always the case that all $\\{p,q\\}$-spirals
are _unique_ extremal animals. In the $\\{4,5\\}$-tessellation, for example,
it is straightforward to construct an animal with $9$ tiles which is extremal,
but not equivalent to $S_{4,5}(9)$, up to isometries. Note that in this
setting $A_{p,q}(2)$ has 13 tiles, and tiles which are incident to only a
vertex of $A_{p,q}(1)$ naturally appear in pairs in the corners. Then let $A$
be an animal obtained by removing two of these corner pairs. It is simple to
compute that both $A$ and $S_{4,5}(9)$ will have $e_{1}=16$, and since they
also have the same number of tiles, all other graph parameters will also be
equal. Hence $A$ is also extremal. Depicted in Figure 10, we see that there
are exactly five distinct extremal $\\{p,q\\}$-animals with 9 tiles up to
isometries, where the image on the far left is $S_{4,5}(9)$.

##  7\. Conclusions and open problems

Recall that Theorem 1.7 asserts that $\mathcal{P}_{p,q}(n)$, the minimum
perimeter that an $n$-tile $\\{p,q\\}$-animal can attain, is equal to
$e_{1}(n)$. Although here we give an algorithm to iteratively find the values
of $\mathcal{P}_{p,q}(n)$, it remains as an open problem to find closed
formulas for $\mathcal{P}_{p,q}(n)$ in the hyperbolic cases. The substitution
rules seen in Section 3 hint at the theory of Sturmian words as a promising
approach to finding such formulas. Nevertheless, we can derive some
interesting properties of $\mathcal{P}_{p,q}$ as a direct consequence of
Corollary 4.4 and Theorem 1.7. For instance, we have that
$\mathcal{P}_{3,q}(n)-\mathcal{P}_{3,q}(n)=\pm 1$ for $q\geq 6$,
$\mathcal{P}_{p,q}(n)$ is non-decreasing when $p=4$ or $\\{p,q\\}=\\{6,3\\}$,
and $\mathcal{P}_{p,q}(n)$ is strictly increasing otherwise. These properties
are summarized in the following Corollary.

######  Corollary 7.1.

For any $\\{p,q\\}$ with $(p-2)(q-2)\geq 4$,

$\displaystyle\mathcal{P}_{p,q}(n+1)-\mathcal{P}_{p,q}(n)=p-2\text{ or $p-4$,
when $q>3$.}$
$\displaystyle\mathcal{P}_{p,3}(n+1)-\mathcal{P}_{p,3}(n)=p-4\text{ or $p-6$,
for $n>1$.}$

In the hyperbolic case, the minimum perimeter is of the order of the number of
tiles. Bounds for $\mathcal{P}_{p,q}(n)$ for sufficiently large $n$ can be
obtained from the following corollary to Theorem 1.5 bounding $e_{2}(n)$.

######  Corollary 7.2.

For $p\geq 4$ and $n>\check{n}(3)$, we have

$\displaystyle n+\frac{n-1}{q-2}\leq e_{2}(n)\leq n+\frac{n-1}{q-3}.$

For $p=3$ and $n>\check{n}(4)$, we have

$\displaystyle n+\frac{n-1}{q-3}\leq e_{2}(n)\leq n+\frac{n-1}{q-4}.$

###### Proof.

For $p\geq 4$, it can be checked that
$\check{n}(k)+\dfrac{\check{n}(k)}{q-2}+1\leq\check{e}_{2}(k)\leq\check{n}(k)+\dfrac{\check{n}(k)}{q-3}$,
for $k\geq 3$. As usual, given $n$ choose $k$ such that
$\check{n}(k)<n<\check{n}(k+1)$. In this case, each $d_{k,i}=2$ or $d_{k,i}=3$
so, Formula $(\ref{eqn:formula-m})$ gives the following bound

$\displaystyle m(q-3)$ $\displaystyle\leq\sum_{i=1}^{m}(q-d_{k,i})\leq
n-\check{n}(k)-1<\sum_{i=1}^{m+1}(q-d_{k,i})\leq(m+1)(q-2),$
$\displaystyle\Longrightarrow\hskip 28.45274pt$
$\displaystyle\frac{n-\check{n}(k)-1}{q-2}-1\leq
m\leq\frac{n-\check{n}(k)-1}{q-3}$

Then, the bounds for $\check{e}_{2}(k)$ and $m$, together with the formula
$e_{2}(n)=n-\check{n}(k)+\check{e}_{2}(k)+m$ gives the result. The analysis
for $p=3$ is analogous. ∎

We further conjecture a sharp limit for this ratio, based on the ratio for the
$A_{p,q}(k)$ sequence.

######  Conjecture 7.3.

$\lim_{n\to\infty}\frac{e_{2}(n)}{n}=\lim_{k\to\infty}\frac{\check{e}_{2}(k)}{\check{n}(k)}=\frac{q-1}{q-2}+\frac{1}{\alpha(q-2)}$

Recall that $e_{2}(n)$ increments by the gluing parameter of each tile. So
when $q=3$, all tiles are either 2-glued or 3-glued, and thus

$\dfrac{e_{2}(n)}{n}=\dfrac{2n+(\\#\text{ of 3-glued
tiles})}{n}=2+\dfrac{\\#\text{ of 3-glued tiles}}{n}.$

And similarly when $q\geq 4$ all tiles are either 1-glued or 2-glued, and the
ratio is

$\frac{e_{2}(n)}{n}=1+\dfrac{\\#\text{ of 2-glued tiles}}{n}.$

So this limit is capturing the ratio of these maximally glued tiles in each
case. If this limit holds, then all such ratios for the graph parameters of
$S_{p,q}(n)$ will also have limits given by the corresponding subsequences for
$A_{p,q}(k)$.

One application of finding exact formulas for $\mathcal{P}_{p,q}(n)$ is to
explore extremal topological animals. Euclidean animals with minimum perimeter
have provided the right shape to produce animals with maximally many holes. We
expect that the same will hold true for hyperbolic animals. Represent the
maximum number of holes that a $\\{p,q\\}$-animal with $n$ tiles can have by
$f_{p,q}(n)$. Then, using techniques introduced in [17], the following
topological isoperimetric inequality holds

(7.4) $\displaystyle
f_{p,q}(n)\leq\frac{np-2(n-1)-\mathcal{P}_{p,q}(n+f_{p,q}(n))}{p}.$

This also provides a measure of certain geometric efficiencies, which are
optimized when $f_{p,q}(n)$ attains this upper bound. In the Euclidean case,
much of the analysis in solving the question of how many holes an $n$-tile
animal can have stemmed from understanding these efficiencies, and analyzing
the gap between $f_{p,q}(n)$ and this bound [17, 18, 19].

Finally, it is also natural to ask about algebraic characterizations of
combinatorial parameters of higher dimensional extremal animals. For example,
one can consider face-minimization properties of structures that are built by
gluing together $d$-dimensional polytopes along codimension-1 faces in
$\mathbb{R}^{d}$ or $\mathbb{H}^{d}$. In these settings, the analogs of the
complete layered animals are straightforward to construct, but it is not
immediately clear, for instance, how to generalize the 2-dimensional spirals
that interpolate between them.

### Acknowledgements

This project received funding from the European Union’s Horizon 2020 research
and innovation program under the Marie Skłodowska-Curie grant agreement No.
754462.

## References

  * Barequet and Shalah [2021] G. Barequet and M. Shalah.  Improved upper bounds on the growth constants of polyominoes and polycubes.  In _Latin American Symposium on Theoretical Informatics_ , pages 532–545. Springer, 2021.
  * Barequet et al. [2019] G. Barequet, M. Shalah, and Y. Zheng.  An improved lower bound on the growth constant of polyiamonds.  _Journal of Combinatorial Optimization_ , 37(2):424–438, 2019.
  * Boettcher et al. [2021] I. Boettcher, A. V. Gorshkov, A. J. Kollár, J. Maciejko, S. Rayan, and R. Thomale.  Crystallography of hyperbolic lattices.  _arXiv preprint arXiv:2105.01087_ , 2021.
  * Bowen [2002] L. Bowen.  Circle packing in the hyperbolic plane.  In _Mathematical Physics Electronic Journal: (Print Version) Volumes 5 and 6_ , pages 161–170. World Scientific, 2002.
  * Breuckmann et al. [2017] N. P. Breuckmann, C. Vuillot, E. Campbell, A. Krishna, and B. M. Terhal.  Hyperbolic and semi-hyperbolic surface codes for quantum storage.  _Quantum Science and Technology_ , 2(3):035007, 2017.
  * Buchholz and de Launey [2009] R. H. Buchholz and W. de Launey.  An edge-minimization problem for regular polygons.  _The Electronic Journal of Combinatorics_ , 16(1), 2009\.  ISSN 10778926.
  * Harary and Harborth [1976] F. Harary and H. Harborth.  Extremal animals.  _J. Combinatorics Information Syst. Sci._ , 1(1):1–8, 1976.
  * Harborth [1974] H. Harborth.  Lösung zu problem 664a.  _Elem. Math_ , 29:14–15, 1974.
  * Higuchi and Shirai [2003] Y. Higuchi and T. Shirai.  Isoperimetric constants of (d, f)-regular planar graphs.  _Interdisciplinary Information Sciences_ , 9(2):221–228, 2003.
  * Jahn and Eisert [2021] A. Jahn and J. Eisert.  Holographic tensor network models and quantum error correction: A topical review.  _Quantum Science and Technology_ , 2021.
  * Jensen [2003] I. Jensen.  Counting polyominoes: A parallel implementation for cluster computing.  In _International Conference on Computational Science_ , pages 203–212. Springer, 2003.
  * Kahle and Roldán [2019] M. Kahle and E. Roldán.  Polyominoes with maximally many holes.  _Geombinatorics_ , 29(1):5–20, 2019.  ISSN 1065-7371.
  * Keller and Peyerimhoff [2008] M. Keller and N. Peyerimhoff.  Geometric and spectral properties of locally tessellating planar graphs.  _arXiv preprint arXiv:0805.1683_ , 2008.
  * Kollár et al. [2019] A. J. Kollár, M. Fitzpatrick, and A. A. Houck.  Hyperbolic lattices in circuit quantum electrodynamics.  _Nature_ , 571(7763):45–50, 2019.
  * Kurz [2008] S. Kurz.  Counting polyominoes with minimum perimeter.  _Ars Combinatoria_ , 88:161–174, 2008.
  * Maciejko and Rayan [2021] J. Maciejko and S. Rayan.  Hyperbolic band theory.  _Science Advances_ , 7(36), 2021.
  * Malen and Roldán [2020] G. Malen and É. Roldán.  Extremal topological and geometric problems for polyominoes.  _The Electronic Journal of Combinatorics_ , 27(2), 2020\.
  * Malen and Roldán [July 2020] G. Malen and E. Roldán.  Polyiamonds attaining extremal topological properties i.  _Geombinatorics_ , pages Vol XXX(Issue I):14–24, July 2020.
  * Malen and Roldán [October 2020] G. Malen and E. Roldán.  Polyiamonds attaining extremal topological properties ii.  _Geombinatorics_ , pages Vol XXX(Issue II):64–76, October 2020.
  * [20] G. Malen, E. Roldán, and R. Toalá-Rodríguez.  Extremal hyperbolic animals.  URL https://www.erikaroldan.net/extremal-p-q-animals.
  * Mansour and Rastegar [2021] T. Mansour and R. Rastegar.  Enumeration of various animals on the triangular lattice.  _European Journal of Combinatorics_ , 94:103294, 2021.
  * Mertens and Moore [2017] S. Mertens and C. Moore.  Percolation thresholds in hyperbolic lattices.  _Physical Review E_ , 96(4):042116, 2017.
  * Shalah and Barequet [2017] M. Shalah and G. Barequet.  _Formulae and growth rates of animals on cubical and triangular lattices_.  PhD thesis, Computer Science Department, Technion, 2017.
  * Sloane et al. [2003] N. J. Sloane et al.  The on-line encyclopedia of integer sequences, 2003.


journaltitleProceedings of the 2021 CHI Conference on Human Factors in Computing Systems
seriesCHI '21
titleHuman Reliance on Machine Learning Models When Performance Feedback is Limited: Heuristics and Risks
Machine learning,appropriate reliance,human-AI interaction

Hoboken, NJ

titleTrust and Power

American Psychological Association

journaltitlePsychological methods
titlePower analysis and determination of sample size for covariance structure modeling

issn0006-3444, 1464-3510
titleMeasures of Multivariate Skewness and Kurtosis with Applications

Briarcliff Manor, NY, USA

Academy of Management

journaltitleAcademy of Management Review
titleAn Integrative Model of Organizational Trust

New York, NY

Psychology Press

titleTest theory: A unified treatment

Taylor & Francis

journaltitleInternational journal of electronic commerce
titleWhat trust means in e-commerce customer relationships: An interdisciplinary conceptual typology

American Psychological Association

journaltitlePsychological methods
titleIdentifying careless responses in survey data.

Los Angeles, CA, USA

Sage Publications

journaltitleHuman Factors
titleAffective Processes in Human–Automation Interactions

journaltitlearXiv: Human-Computer Interaction
noteRetrieved from <https://arxiv.org/abs/1811.11839>
titleA Multidisciplinary Survey and Framework for Design and Evaluation of Explainable AI Systems

Berlin, Germany

Springer Berlin, Heidelberg

titleTesttheorie und Fragebogenkonstruktion [Test Theory and Questionnaire Construction]

Taylor & Francis

titleTrust in automation: Part I. Theoretical issues in the study of trust and human intervention in automated systems

New York, NY, USA

Association for Computing Machinery

journaltitleCommun. ACM
titleTo Trust or to Distrust, That is the Question: Investigating the Trust-Distrust Paradox

Los Angeles, CA, USA

Sage Publications

journaltitleHuman Factors
titleHumans and Automation: Use, Misuse, Disuse, Abuse

journaltitleBehavior Research Methods
titleData quality of platforms and panels for online behavioral research

Hamburg, Germany

Association for Computing Machinery

journaltitleExtended Abstracts of the 2023 CHI Conference on Human Factors in Computing Systems
seriesCHI EA '23
titleTrust Issues with Trust Scales: Examining the Psychometric Quality of Trust Measures in the Context of AI

Taylor     Francis

journaltitleInternational Journal of Human–Computer Interaction
titleDevelopment and Validation of a Positive-Item Version of the Visual Aesthetics of Websites Inventory: The VisAWI-Pos

Springer Nature Switzerland

booktitleExplainable Artificial Intelligence
titleThe Importance of Distrust in AI

Yokohama, Japan

abstractWith machine learning models being increasingly used to aid decision making even in high-stakes domains, there has been a growing interest in developing interpretable models. Although many supposedly interpretable models have been proposed, there have been relatively few experimental studies investigating whether these models achieve their intended effects, such as making people more closely follow a model’s predictions when it is beneficial for them to do so or enabling them to detect when a model has made a mistake. We present a sequence of pre-registered experiments (N = 3, 800) in which we showed participants functionally identical models that varied only in two factors commonly thought to make machine learning models more or less interpretable: the number of features and the transparency of the model (i.e., whether the model internals are clear or black box). Predictably, participants who saw a clear model with few features could better simulate the model’s predictions. However, we did not find that participants more closely followed its predictions. Furthermore, showing participants a clear model meant that they were less able to detect and correct for the model’s sizable mistakes, seemingly due to information overload. These counterintuitive findings emphasize the importance of testing over intuition when developing interpretable models.
journaltitleProceedings of the 2021 CHI Conference on Human Factors in Computing Systems
seriesCHI '21
titleManipulating and Measuring Model Interpretability
human-centered machine learning,machine-assisted decision making,interpretability
family=R Core Team,

Vienna, Austria

R Foundation for Statistical Computing

titleR: A Language and Environment for Statistical Computing

Briarcliff Manor, NY, USA

Academy of Management Briarcliff Manor, NY 10510

journaltitleAcademy of Management Review
titleNot So Different After All: A Cross-Discipline View Of Trust

Sage Publications Sage UK: London, England

journaltitleHuman Relations
titleTrust and distrust: Polar opposites, or independent but co-existing?

Vancouver, BC, Canada

Association for Computing Machinery

journaltitleProceedings of the SIGCHI Conference on Human Factors in Computing Systems
seriesCHI '11
titleWhen Designing Usability Questionnaires, Does It Hurt to Be Positive?

Boston, MA

Springer US

booktitleRobust Intelligence and Trust in Autonomous Systems
titleMeasuring Trust in Human Robot Interactions: Development of the "Trust Perception Scale-HRI"

Chicago, IL, USA

Association for Computing Machinery

abstractAuditing plays a pivotal role in the development of trustworthy AI. However, current research primarily focuses on creating auditable AI documentation, which is intended for regulators and experts rather than end-users affected by AI decisions. How to communicate to members of the public that an AI has been audited and considered trustworthy remains an open challenge. This study empirically investigated certification labels as a promising solution. Through interviews (N = 12) and a census-representative survey (N = 302), we investigated end-users’ attitudes toward certification labels and their effectiveness in communicating trustworthiness in low- and high-stakes AI scenarios. Based on the survey results, we demonstrate that labels can significantly increase end-users’ trust and willingness to use AI in both low- and high-stakes scenarios. However, end-users’ preferences for certification labels and their effect on trust and willingness to use AI were more pronounced in high-stake scenarios. Qualitative content analysis of the interviews revealed opportunities and limitations of certification labels, as well as facilitators and inhibitors for the effective use of labels in the context of AI. For example, while certification labels can mitigate data-related concerns expressed by end-users (e.g., privacy and data protection), other concerns (e.g., model performance) are more challenging to address. Our study provides valuable insights and recommendations for designing and implementing certification labels as a promising constituent within the trustworthy AI ecosystem.
journaltitleProceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency
seriesFAccT '23
titleCertification Labels for Trustworthy AI: Insights From an Empirical Mixed-Method Study
Seal,User study,Certification,Trust,Documentation,AI,Label,Trustworthy,Audit

Hamburg, Germany

Association for Computing Machinery

journaltitleCHI 2023 TRAIT Workshop on Trust and Reliance in AI-Human Teams
titleDistrust in (X)AI – Measurement Artifact or Distinct Construct?

Virtual/New Orleans, LA, USA

Association for Computing Machinery

journaltitleCHI TRAIT Workshop
titleTrust and Reliance in XAI–Distinguishing Between Attitudinal and Behavioral Measures

titleA Micro and Macro Perspective on Trustworthiness: Theoretical Underpinnings of the Trustworthiness Assessment Model (TrAM)

journaltitleComputers in human behavior
titleTrust and distrust on the web: User experiences and website characteristics

journaltitleOrganization science
titleExplaining the limited effectiveness of legalistic “remedies” for trust/distrust

Los Angeles, USA

SAGE Publications

journaltitleProceedings of the Human Factors and Ergonomics Society Annual Meeting
titleTowards an Empirically Developed Scale for System Trust: Take Two

Virtual Event, Canada

Association for Computing Machinery

abstractEnvironmental data science is uniquely placed to respond to essentially complex and fantastically worthy challenges related to arresting planetary destruction. Trust is needed for facilitating collaboration between scientists who may share datasets and algorithms, and for crafting appropriate science-based policies. Achieving this trust is particularly challenging because of the numerous complexities, multi-scale variables, interdependencies and multi-level uncertainties inherent in environmental data science. Virtual Labs—easily accessible online environments provisioning access to datasets, analysis and visualisations—are socio-technical systems which, if carefully designed, might address these challenges and promote trust in a variety of ways. In addition to various system properties that can be utilised in support of effective collaboration, certain features which are commonly seen to benefit trust—transparency and provenance in particular—appear applicable to promoting trust in and through Virtual Labs. Attempting to realise these features in their design reveals, however, that their implementation is more nuanced and complex than it would appear. Using the lens of affordances, we argue for the need to carefully articulate these features, with consideration of multiple stakeholder needs on balance, so that these Virtual Labs do in fact promote trust. We argue that these features not be conceived as widgets that can be imported into a given context to promote trust; rather, whether they promote trust is a function of how systematically designers consider various (potentially conflicting) stakeholder trust needs.
journaltitleProceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency
seriesFAccT '21
titleFifty Shades of Grey: In Praise of a Nuanced Approach Towards Trustworthy Design
Environmental Data Science,Trust,Affordances,Virtual Research Environments

New York, NY

journaltitleProceedings of the 2020 Conference on Fairness, Accountability, and Transparency
titleThe Relationship Between Trust in AI and Trustworthy Machine Learning Technologies

New Orleans, LA, USA

Association for Computing Machinery

journaltitleExtended Abstracts of the 2022 CHI Conference on Human Factors in Computing Systems
seriesCHI EA '22
titleTrust in Human-AI Interaction: Scoping Out Models, Measures, and Methods
Decision aids,Scoping review,Robots,Automation,Trust,Artificial intelligence

New York, NY, USA

Association for Computing Machinery

journaltitleProc. ACM Hum.-Comput. Interact.
titleHow to Evaluate Trust in AI-Assisted Decision Making? A Survey of Empirical Methodologies
methodology,decision making,trust,artificial intelligence

journaltitleFuzzy Sets and Systems
titleGradual trust and distrust in recommender systems

American Psychological Association

journaltitleJournal of personality and social psychology
titleDevelopment and validation of brief measures of positive and negative affect: the PANAS scales.

journaltitleJournal on Multimodal User Interfaces
title“Let me explain!”: exploring the potential of virtual agents in explainable AI interaction design

New York, NY

titleA beginner's guide to structural equation modeling

Hamburg, Germany

Association for Computing Machinery

journaltitleProceedings of the 2023 CHI Conference on Human Factors in Computing Systems
seriesCHI '23
titleMeasuring and Understanding Trust Calibrations for Automated Systems: A Survey of the State-Of-The-Art and Future Directions
automation,warranted trust,trust calibration,survey,empirical studies

Glasgow, Scotland Uk

Association for Computing Machinery

journaltitleProceedings of the 2019 CHI Conference on Human Factors in Computing Systems
seriesCHI '19
titleUnderstanding The Effect of Accuracy on Trust in Machine Learning Models

Limassol, Cyprus

Association for Computing Machinery

journaltitleProceedings of the 22nd international conference on intelligent user interfaces
seriesIUI '17
titleUser Trust Dynamics: An Investigation Driven by Differences in System Performance