Proof of radlam Classification

Enough talk, let’s do some math.

Sketch of proof of the classification theorem given in The Graph Type of a Polyomino. (I defined radlams in the post Raldams.):

First we need some lemmas on how radlams decompose.

Lemma 1 (the Anthony Decomposition): Removing a domino from a radlam leaves radlams as the remaining components (pieces). That is, if R is a radlam containing a domino D then R-D consists of one or more polyominoes, each of which is a radlam.

Proof of Lemma 1: Let P be a component of R-D. Suppose that D’ is a domino in P (if there are none, then P is a monomino, which is a radlam and we are done). Now consider R-D’. Since R is a radlam, at least one component of R-D’ is a monomino. Call this monomino M. The claim is that M is a component of P-D’. There are two things to check: (1) M is contained in P and (2) M is not connected to any other squares in P-D’. I will let you convince yourself of facts (1) and (2).

In fact, the proof of Lemma 1 doesn’t actually use the fact that D is a domino. All it uses is the fact that D is not a monomino. (The problem that you run into when D is a monomino is that M may equal D.) So we have shown:

Lemma 2: If R is a radlam and P is a subpolyomino of R, but P is not a monomino, then R-P is a radlam.

Lemma 3: If P is a polyomino containing a domino D and if the components of P-D are all monominoes, then P has size 6 or smaller.

Proof of Lemma 3: It’s pretty easy to convince yourself of this.

Using these lemmas we can prove:

Lemma 4: If R is a radlam of size 3 or larger, then R decomposes into two radlams P and Q, with Q of size six or smaller and neither P nor Q of size zero

Proof of Lemma 4: Check all radlams up through size 6 by hand. Thus, we assume that R has size 7 or greater. Remove a domino D from R. Since R is of size 7 or greater at least one component of R-D must be larger than a monomino. Call this component Q’. Now P’:=R-Q’ is connected. If Q’ has size 6 or smaller, then we are done. If not, then choose domino D’ in Q’, such that D’ is adjacent to P’. Then Q’-D’ consists of radlams, at least one of which is larger than a monomino (since Q’ was assumed to have at least size 7). Let Q” be one such component of Q’-D’. Let P”=R-Q”. P” is connected because everything in (Q’-D’)-Q” is adjacent to D’, and D’ is adjacent to P’. If Q” has size 6 or smaller we are done. If not, iterate the process.

Now the proof proceeds by induction. Check that the list is complete for radlams up through hexominoes I guess. Assume that the list is complete up through size . To get size you just have to check how you can glue together two radlams P and Q, with Q of size and P of size …and then you’re done!

I’m pretty sure that this proof is correct and I that at some point I checked all the details, but there very well may be holes, so let me know if you find some.