24
$\begingroup$

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?

$\endgroup$
2
  • 6
    $\begingroup$ The paper "Tiling rectangles with T-tetrominoes" by Korn and Pak seems to present some progress for non-rectangular simply-connected regions, mainly Theorem 11 in section 8. It doesn't seem like they have a complete answer though. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.6847 $\endgroup$
    – Alon Amit
    Jun 20, 2010 at 21:57
  • $\begingroup$ See also Korn's thesis, "Geometric and algebraic properties of polyomino tilings". $\endgroup$ Jun 21, 2010 at 1:19

1 Answer 1

25
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Do any of these results provide new obstructions for tilings (as opposed to studying the structure of the set of possible tilings of some regions)? Is there any non-rectangular region which is proved to be non-tilable, but not for colouring reason and not because of some local obstruction (like "there is only one way to cover this square, but then no way to cover that")? $\endgroup$ Jun 21, 2010 at 22:02
  • $\begingroup$ If the question is whether one can extend Walkup's result to "nice" non-rectangular regions, the answer is yes, but only by using his idea again. If the question is whether our local connectivity results imply any non-tileability results, the answer is also yes, but the regions would be rather ugly and actually hard to construct. If the question is whether one should hope for a general algebraic approach, the answer is probably no, or at least that's my intuition. $\endgroup$
    – Igor Pak
    Jun 22, 2010 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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