Exponential bounds for the number of lattice animals with a given boundary.

Question

Hi all,

I am doing a work in collaboration with other mathematicians about phase transition in the Ising model and we need to know if exponential upper bounds exist for the number of lattice animals with boundary of size $n$.

To be precise, consider the square lattice $\mathbb{Z}^2$ as graph where the edges are pairs of points in the lattice having distance one from each other, where the distance is induced by the norm $\|(z_1,z_2)\|=|z_1|+|z_2|$.

We call a lattice animal the set of vertices of any connected subgraph of the square lattice. Given an animal $A$, we denote the boundary of $A$ by $\partial A$, that is, the set of vertices of distance one from $A$.

Fix a site $z\in \mathbb{Z}^2$ and let be
$$ f(n)=\sharp \{A\ \text{is lattice animal}; A\ni z\ \text{and}\ |\partial A|=n\} $$
Is it known if $f(n)=O(e^{k n})$ ?

I learned from google that this problem is also known in the combinatorics community as enumeration of polyominoes with a given site-perimeter.

All the papers I found about the upper bounds at some point have to impose some geometric hypotheses on the polyominoes such as convexity, starcase shape or bargraph shape.

I don't know yet if those hypotheses are being used in order to get sharp upper bounds or if they are the only ones available.

If the question about exponential upper bound is not yet solved, is there a specialist in this area who could tell me what they think about the upper bound for this problem.

Answer 1

I think the following (or something close) proves Leandro’s point:

Let $n=5k$ for some odd integer $k$, and let $B_k$ be the subgraph of $\mathbb{Z}^2$ with vertex set $[1\dots k]\times[1\dots k]$ (and all edges between these vertices from the lattice $\mathbb{Z}^2$). Let K be any subset of $[2\dots k-1]\times[2\dots k-1]$ of size $k$ in which every point has both coordinates even. Let $A_k^K$ be the subgraph of $B_k$ obtained by removing the points of $K$ from the vertex set. The graph $A_k^K$ is an animal, and the boundary of $A_k^K$ has cardinality $n$; the boundary comprises the $4k$ points exterior to and adjacent to $B_k$ (they remain adjacent to $A_k$, because no points on the perimeter of $B_k$ were removed) together with the $k$ points of $K$, each of which is adjacent to a location with at least one odd coordinate. The animals $A_k^K$ and $A_k^{K'}$ are distinct if $K\neq K'$.

Let $\mathcal{A}_k$ be set of $A_k^K$ for all possible sets $K$ described above. Then $f(n) \ge |\mathcal{A}_k|$. (Let $z=(1,1)$). The number of distinct sets $K$ is approximately $k^2 /4\choose k$, which grows faster than $k! = (n/5)!$ and is therefore not bounded by an exponential.

Answer 2

EDIT: I see that Steve has more or less the same construction above. I should have read his answer more carefully before I posted.

I don't believe it's true. Let's say you have a square polyomino with $n/2$ perimeter (so also $n/2$ site-perimeter) and you remove $n/2$ sites from its interior. Not all ways of doing this will give you a lattice animal with site-perimeter $n$, but if you just remove sites where both coordinates are even, you get a lattice animal (i.e., the polyomino will still be connected). The number of ways of doing this are roughly $cn^2 \choose n/2$, which grows as $e^{O(n \log n)}$.

ADDED MATERIAL:

There is an $e^{C n \log n}$ upper bound as well. Again, let's think about polyominos with site perimeter $n$. If we can specify the boundary of such a polyomino with $O(n \log n)$ bits, this gives a $e^{O(n \log n)}$ bound on how many of these there are. We will specify the boundary in two stages. First, let's look at the exterior edges (all the edges which can be connected to $\infty$ by a path of squares not in the polyomino). We can specify these exterior edges by a list of directions: e.g., EESENESSW$\ldots$, which is only $O(n)$ bits.

Now, let's look at the interior boundary edges. There are at most $cn$ of these for some constant $c$, and there are at most $n^2$ edges in the interior of the polynomial (the biggest it can be is an $n/4 \times n/4$ square), so we can specify these by creating some canonical list of the interior edges, and specifying which ones we have. This takes at most $\log_2 \sum_{k=0}^{cn} {n^2 \choose k} = O(n \log n)$ bits, and thus we get an $e^{C n \log n}$ upper bound on the number of these lattice animals.

This leaves the question open of what is $$C=\lim_{n\rightarrow \infty} \frac{\log f(n)}{n \log n}$$ (although it might even be difficult to prove rigorously that this limit exists).

Answer 3

According to Grimmett's book Percolation,

It is well know that the number of animals with $n$ vertices grows at most exponentially as $n \to \infty$. More explicitly, we shall see in the proof of Theorem (4.20) that the total number $T_n$ of animals with $n$ vertices satisfies $T_n \le 7^{dn}$.

(Here $d$ is the dimension of the lattice.)

Since the number of boundary vertices is at most some constant times the number of vertices in the animal itself, this also gives an affirmative answer to your question.