What is the asymptotic behavior of large polyominoes? How many of them tile the plane?

83 Views Asked by At

The free polyominoes on $n$ cells can be classified into three categories: those with holes, those that tile the plane, and those without holes that do not tile the plane. (No polyomino with holes tiles the plane, so the fourth logical category has no members.)

I am curious about the asymptotic behavior of this distribution for large $n$. For $n\le 6$, every polyomino on $n$ cells tiles the plane. However, as $n$ grows larger, this ceases to be the case. Using the values given at this page, I have plotted the ratio of polyominoes in each category for $n\le 25$:

enter image description here

Emprically, the ratio of tiling polyominoes appears to decay exponentially, roughly halving at every increase in $n$; the ratio $1:x$ where $x=2^{n-11}$ matches the observed data quite well.

I also suspect that the polyominoes with holes dominate for very large $n$, in that their ratio approaches 1; one would expect a "generic" large polyomino to have many holes, though I'm not sure how to formalize this intuition and obtain a formal proof. I also don't know what the rate of approach is.

Likewise, it seems obvious that a "generic" large polyomino has no hope of tiling the plane, even conditioned on being simply connected; again, I am unsure how to go about formalizing this intuition into something resembling a proof or a bound on growth.

The relevant OEIS sequences (A000105, A054359, A054360, A001419) do not offer much insight in their comments, either proven results or conjectures. It is mentioned that the total number of polyominoes of order $n$ is known to grow exponentially, with a rate of growth between $3.98$ and $4.64$, but no comments about the growth rates of these subsets are given.

One can at least show that the fraction of size-$n$ polyominoes that tile the plane does not shrink any faster than exponentially; for $n=2k>2$, there are at least $2^{k-2}$ tiling polyominoes which tile by translation, given by placing shifted dominoes in a row: enter image description here This bounds the asymptotic decay of the ratio of tiling polyominoes by $\left(\frac{\sqrt{2}}{4.64}\right)^n$.

Some questions:

  • Can we place nontrivial upper bounds on the number of tiling polyominoes? In particular, can it be proven that they occupy an exponentially-decreasing fraction of the polyominoes, and what bounds can be put on the associated constant? Can we do the same for the fraction of simply connected polyominoes which tile the plane?

  • Can it be rigorously shown that "most" polyominoes have holes in the limit? What can be said about the rate at which the fraction of hole-y polyominoes approaches 1? (For the latter question, I would be interested in heuristic arguments to expect a certain growth rate as well, even if the associated bound cannot be proven.)

  • Is there previous work on this or related questions that can be found?