Sign In

Communications of the ACM

Contributed articles

λ > 4: An Improved Lower Bound on the Growth Constant of Polyominoes

View as: Print Mobile App ACM Digital Library In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
? > 4: An Improved Lower Bound on the Growth Constant of Polyominoes, illustrative photo

Credit: Radachynskyi Serhii

What is λ? The universal constant λ arises in the study of three completely unrelated fields: combinatorics, percolation, and branched polymers. In combinatorics, analysis of self-avoiding walks (SAWs, or non-self-intersecting lattice paths starting at the origin, counted by lattice units), simple polygons or self-avoiding polygons (SAPs, or closed SAWs, counted by either perimeter or area), and "polyominoes" (SAPs possibly with holes, or edge-connected sets of lattice squares, counted by area) are all related. In statistical physics, SAWs and SAPs play a significant role in percolation processes and in the collapse transition that branched polymers undergo when being heated. A collection edited by Guttmann15 gives an excellent review of all these topics and the connections between them. In this article, we describe our effort to prove that the growth constant (or asymptotic growth rate, also called the "connective constant") of polyominoes is strictly greater than 4. To this aim, we exploited to the maximum possible computer resources available to us. We eventually obtained a computer-generated proof that was verified by other programs implemented independently. We start with a brief introduction of the three research areas.

Back to Top

Key Insights


Enumerative combinatorics. Imagine a two-dimensional grid of square cells. A polyomino is a connected set of cells, where connectivity is along the sides of cells but not through corners; see Figure 1 for examples of small polyominoes. Polyominoes were popularized in the pioneering book by Golomb13 and by Martin Gardner's columns in Scientific American; counting polyominoes by size became a popular and fascinating combinatorial problem. The size of a polyomino is the number of its cells.


No entries found

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.