What can be tiled by T-tetrominoes?

2010-06-20T20:18:41Z

The T-tetromino is a T-shaped figure made of four unit squares. An $m\times n$ rectangle can be tiled by T-tetrominoes if and only if both $m$ and $n$ are multiples of 4. This was proved in a 1965 paper by D.W.Walkup, and the proof was "hands on".

Some "algebraic" tricks like colouring or tiling groups can prove that $mn$ must be a multiple of 8, but they do not seem to rule out the cases like $99\times 200$ and $100\times 102$.

I wonder whether a better proof of D.W.Walkup's theorem is known today. By "better" I mean applicable to non-rectangular regions as well. For example, is there a way to determine what 6-gons (8-gons, ...) admit tiling by T-tetrominoes?

Answer by Igor Pak for What can be tiled by T-tetrominoes?

2010-06-21T01:43:46Z

There are only partial answers to this question. First, one can prove that Walkup's result cannot be proved using coloring arguments (I think I did this in New horizons paper, but the setting is formalized in the Ribbon tile invariants paper). Second, Walkup's proof uses an easy induction argument, and it extends to regions with sides multiples of 4. Third, I am pretty sure you can classify all 6- and 8-gons tileable by T-tetrominoes. This won't be conceptual. Why do it then?

Now, motivated by the quest to find a better proof, I made a "local move connectivity" conjecture saying that every two T-tetromino tilings of a simply connected region are connected by a series of moves involving either two T-tetrominoes or four T-tetrominoes (forming a $4\times 4$ square). Usually, the "conceptual proof" comes from some kind of height function argument which also proves the local move connectivity. Now, Mike Korn in his thesis disproved this by a simple construction. One can ask if the Conway group approach in full generality can prove something like what you are asking. You need to compute $F_2/\langle tile~words\rangle$ (see Conway-Lagarias paper, "New horizons" or Korn's thesis). We did not do that, but I won't be very optimistic - it is a bit of a miracle when this approach works out.

Mike and I were still able to prove the conjecture (by a height function argument) for rectangles and the above mentioned 4-multiple regions, but that proof assumes Walkup's theorem. Independently this was established by Makarychev brothers, using a related but somewhat different argument (in Russian, based on connection to the six-vertex model). In fact, in a followup paper we use Walkup's theorem as a definition of the graphs in which the number of claw partitions is "nice". Anyway, hope this helps.

UPDATE: I just remembered that Michael Reid also did the T-tetromino computation (as well as many other computations) here.

What can be tiled by T-tetrominoes? - MathOverflow

What can be tiled by T-tetrominoes?

Answer by Igor Pak for What can be tiled by T-tetrominoes?