21
$\begingroup$

A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the tatami condition if no four tiles meet at any point. (Or you can think of it as the removal of a matching from a grid graph that breaks all $4$-cycles).

This simple restriction, brought to my attention by Don Knuth in Vol 4 of TAOCP, became my PhD thesis topic, when my research group and I discovered that it imposes a aesthetically pleasing structure with a nice description, and opened up lots of fun questions.

Here is my favourite example, which has all of the possible "features". First it is shown uncoloured

    A tatami tiling showing all possible features, up to rotation (source)

And here it is coloured

    A tatami tiling showing all possible features, up to rotation (source)

The magenta tiles show the types of features it can have, and here they are on their own:

    Loner and Vee features (source)

    Bidimer and vortex features (source)

I'll introduce my question here, and then summarize some more results later. I want to find more and better ties between tatami tilings and other less esoteric math problems. If you think of a paper or subject I might want to look into, don't hesitate to answer.

In our first paper, we proved the above structure and showed that:

  1. A tiling is described by the tiles on its boundary, and hence has a description that is linear in the dimensions of the grid.
  2. The maximum number of monomers is at most max(r+1,c+1), and this is achievable.
  3. We found an algorithm for finding the rational generating polynomial of the numbers of tilings of height r (which I think can also be calculated with the transfer matrix method).

We posed a couple of complexity questions (which I am working on), for example, is it NP-hard to reconstruct a tatami tiling given its row and column projections?

    Tomoku game. Is it NP-hard? (source)

Or tile a given orthogonal region with no monomers?

    Water striders. Is it NP-hard? (source)

Next we focused on enumerating tilings of the $n\times n$ grid, and found a partition of $n\times n$ tiles with the maximum number of monomers into $n$ parts of size $2^{n-1}$. We also counted the number tilings with $k$ monomers, and this curious consequence:

The number of $n \times n$ tatami tilings is equal to the sum of the squares of all parts in all compositions of $n$. That is, $2^{n-1}(3n-4)+2$.

We also found an algorithm to generate the ones with $n$ monomers, and a Gray code of sorts.

Nice numbers, and a cute problem, but another paper that is self contained with elementary (albeit, somewhat complicated) reasoning.

Our third paper in this story (in preparation), looks at the generating polynomial for $n\times n$ tilings with $n$ monomers whose coefficients are the number of tilings with exactly $v$ vertical dimers (or $h$ horizontal dimers). It turns out this generating polynomials is a product of cyclotomic polynomials, and a somewhat mysterious and seemingly irreducible polynomial, who's complex roots look like this:

    Complex roots of mysterious polynomial (source)

We've found a bunch of neat stuff about it, for example the evaluation of this polynomial at $-1$ is $\binom{2n}{n}$, for $2(n+1)\times 2(n+1)$ tilings, and we found our generating polynomial gives an algorithm to generate the tilings in constant amortized time. Here is some output of the implementation:

    Output of cat algorithm generating tilings. This is genVH(8,7), for <span class=$8\times 8$ tilings with $8$ monomers and $7$ vertical dimers." /> (source)

That's the most of the published (and almost published) story. There is a loose connection with other monomer-dimer problems, and things I can look into, like Aztec tatami tilings, but I'm looking for direct applications of other results to these, or vice versa, especially with this last paper in preparation. I'm not asking you to do research for me, but just your thoughts as they are now, so I can go learn new stuff.

Feel free to comment about what you think is interesting, or not, about tatami tilings too!

Improve this question
$\endgroup$
9
  • $\begingroup$ In "Monomer-dimer tatami tilings of square regions," Theorem 1 lists conditions under which $T(n,m) = 2^n (3n+2).$ For at least $n = 1, \ldots, 8,$ these numbers (respectively, $10, 32, 88, 224, 544, 1280, 2944, 6656$) appear in one of the diagonals of oeis.org/A059473/table when displayed as a triangular array. Whether this is trivial or significant I cannot say at the moment, but perhaps this is something worth investigating. $\endgroup$
    – Benjamin Dickman
    Commented Aug 2, 2012 at 2:47
  • 8
    $\begingroup$ All this looks interesting, but where is the QUESTION? $\endgroup$
    – Alexandre Eremenko
    Commented Dec 8, 2012 at 19:46
  • 1
    $\begingroup$ Tilings like this lead to dynamical systems called tiling spaces, with an associated shift action of $\mathbb{Z}^2$, suggesting a large range of dynamical questions, e.g., (1) are the periodic points dense, (2) what is the entropy, and (3) is the system ergodic or mixing? For the standard dimer tilings these questions have very interesting answers, including the calculation of entropy, which turns out to be the Mahler measure of an associated 2-variable polynomial. $\endgroup$
    – Douglas Lind
    Commented Aug 8, 2014 at 13:30
  • 1
    $\begingroup$ I guess monomers are simply single "small" squares $\ 1\times 1,\ $ and *dimers* are just "domino rectangles" $\ 2\times 1$ or $\ 1\times 2$? True? $\endgroup$
    – Włodzimierz Holsztyński
    Commented Sep 7, 2014 at 5:33
  • 3
    $\begingroup$ I wish the QUESTION would include a clearly distinct separate section with questions only. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Sep 7, 2014 at 5:36

1 Answer 1

Reset to default
1
$\begingroup$

Tilings in relation to undecidability has been on MO before, (see Wang tiles). Perhaps, if you look at unbounded regions, can some questions about tileability be undecidable?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .