What can be tiled by T-tetrominoes? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T04:30:46Z http://mathoverflow.net/feeds/question/28883 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/28883/what-can-be-tiled-by-t-tetrominoes What can be tiled by T-tetrominoes? Sergei Ivanov 2010-06-20T20:18:41Z 2011-06-16T07:46:55Z <p>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 <strong>only if</strong> 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".</p> <p>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$.</p> <p>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?</p> http://mathoverflow.net/questions/28883/what-can-be-tiled-by-t-tetrominoes/28897#28897 Answer by Igor Pak for What can be tiled by T-tetrominoes? Igor Pak 2010-06-21T01:43:46Z 2010-06-21T12:02:12Z <p>There are only partial answers to this question. First, one can <em>prove</em> that Walkup's result cannot be proved using coloring arguments (I think I did this in <a href="http://www.math.ucla.edu/~pak/papers/tilesurvey.ps" rel="nofollow">New horizons</a> paper, but the setting is formalized in the <a href="http://www.math.ucla.edu/~pak/papers/tile.pdf" rel="nofollow">Ribbon tile invariants</a> 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? </p> <p>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 <em>height function</em> argument which also proves the local move connectivity. Now, Mike Korn in his <a href="http://dspace.mit.edu/handle/1721.1/16628" rel="nofollow">thesis</a> disproved this by a simple construction. One can ask if the <em>Conway group</em> approach in full generality can prove something like what you are asking. You need to compute $F_2/\langle tile~words\rangle$ (see <a href="http://linkinghub.elsevier.com/retrieve/pii/0097316590900574" rel="nofollow">Conway-Lagarias</a> 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. </p> <p>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 <a href="http://www.cs.princeton.edu/~kmakaryc/pdf/tetro.pdf" rel="nofollow">established</a> by Makarychev brothers, using a related but somewhat different argument (in Russian, based on connection to the six-vertex model). In fact, in a <a href="http://www.math.ucla.edu/~pak/papers/tutte7color.pdf" rel="nofollow">followup paper</a> we use Walkup's theorem as a definition of the graphs in which the number of claw partitions is "nice". Anyway, hope this helps. </p> <p>UPDATE: I just remembered that Michael Reid also did the T-tetromino computation (as well as many other computations) <a href="http://www.math.ucf.edu/~reid/Research/Tilehomotopy/tilehomotopy.pdf" rel="nofollow">here</a>. </p>