Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Maybe I'm making a silly mistake, but can't you bound this from above by the number of distinct subtrees of the infinite rooted 4-ary tree (everyone has three children except the root who has 4 children) having $n$ external vertices? The latter is bounded from above by 3^n, i think, so the number is certainly at most exponential. –  Louigi Addario-Berry Feb 16 '11 at 19:25
    
Hi Louigi, if we have a lattice animal with $n$ boundary points, how to associate it to a tree with $n$ external vertices in order to define an injective map ? –  Leandro Feb 16 '11 at 20:33
    
Well, give numbers to the compass directions: 1=N, 2=E, 3=S, 4=W. Then among all (rooted at z) spanning trees of your animal, choose the one that is lexicographically least. (You can see this, for example, as the union over all sites v in the animal of the lexicographically least path from z to v. I think.) But this only works to give an exponential bound in terms of the size of the animal, not the size of its boundary. Steve Kass's example exploits the (potential) difference between these sizes quite nicely. –  Louigi Addario-Berry Feb 16 '11 at 21:22
add comment

3 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
Perhaps instead of looking at f(n) with boundary size exactly n, you can get asymptotics on g(n) with boundary size at most n. Then you can take the above example, "fill in the holes" and use the literature to get a bound on g(n) which will be useful for f(n). Gerhard "Ask Me About System Design" Paseman, 2011.02.16 –  Gerhard Paseman Feb 16 '11 at 22:01
    
Sorry about that Steve, your argument is perfect and now it is clear for me. Thank you very much to spend this time explaining me again and again the same thing. I am erasing my comments because they are not given any contribution for your answer. Thanks again. –  Leandro Feb 17 '11 at 2:09
add comment

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).

share|improve this answer
2  
It's also not too hard to show that there is also an $e^{C n \log n}$ upper bound for some constant $C$, so this is the right growth rate for these beasts. –  Peter Shor Feb 17 '11 at 4:17
    
Thanks for this information Peter. Could you give some hint on how one can show this ? –  Leandro Feb 17 '11 at 15:48
    
I could edit my answer to include this result, but probably not until tomorrow or Saturday (I'm too busy before then). –  Peter Shor Feb 17 '11 at 18:08
    
Thanks Peter for the explanation. I thinking on how to compute the constant $C$ very interesting question. –  Leandro Feb 22 '11 at 0:22
add comment

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.

share|improve this answer
1  
Hi Matthew I do remember this result, but I think that we can not argue like that. Let me call $B_n$ the number of lattice animals with $n$ boundary points. Animals like that can have from $(n-2)$ up to $\frac{n^2}{4}$ vertices so if I take the greatest upper bound I got exponential of $n^2$ and not $n$ as I am needing. Am I right ? –  Leandro Feb 16 '11 at 20:07
    
Leandro, you are right. I will think about this some more... –  Matthew Kahle Feb 16 '11 at 20:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.