59
$\begingroup$

I just finished teaching a class in combinatorics in which I included a fairly easy upper bound on the number of domino tilings of a region in the plane as a function of its area. So this led to this question, which I suspect is an open problem: Does a $2n \times 2n$ square have the most domino tilings among all regions with area $4n^2$? I aired this question in a mailing list, which is one reason that I think that it's an open problem. The discussion there did lead to a great answer from Rick Kenyon, who says that using his methods, the conjecture is asymptotically true for dilated rectilinear regions. (In other words, if you take any fixed polyomino and dilate it by a sufficiently large factor, then it will have fewer tilings than a square with the same area or very slightly less area.)

Still, I just came up with the question in my class, so I don't really know if it's open or previously stated. (This is my excuse for posting it MO.) I Googled some, without success. It is also easy to pose generalizations:

(1) The inequality might also hold for regions that map to the plane with multiple sheets (immersions) or branch points, at least when such regions are topological disks and the branch points are at vertices of the tiling by unit squares. (Kenyon's methods might also apply to these cases.)

(2) Does the $d$-dimensional cube $[0,2n]^d$ have the most tilings by domino bricks, among all regions in $\mathbb{R}^d$ with volume $(2n)^d$?

(3) Given an integer $k > 2$, does a $kn \times kn$ square have the most tilings by $k \times 1$ rectangles, among regions with area $k^2n^2$?

(4) Mutual generalizations of (1)-(3), and tilings by a rectangular brick with some other shape.

Kenyon's work is a (deep) extension of the permanent-determinant method of Kasteleyn and Percus to count matchings of a planar graph, so it would not apply to cases (2) and (3).

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Just for everyone's information, OEIS A004003 counts the number of domino tilings of the $2n \times 2n$ square: $1, 2, 36, 6728, 12988816, 258584046368, \ldots$. Several possibly relevant references are listed there. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 1, 2014 at 10:48
  • 3
    $\begingroup$ For small values of $N$, shapes with $2N$ squares which maximize the number of tilings by $N$ dominoes seem to be the following rectangles: 2×1, 2×2, 2×3, 2×4, 2×5, 2×6 (not the squarer 3×4). But 4×4 (36 tilings) is better than 2×8 (34 tilings), consistent with your conjecture. $\endgroup$
    – Bruno Le Floch
    Commented Nov 20, 2014 at 22:29
  • 3
    $\begingroup$ (3) The $8\times8$ square has two tilings by $8\times 1$ rectangles, but a region consisting of two $9\times 9$ squares with inner $7\times 7$ squares removed has four tilings. I don't think there is anything similar for $n>1$. $\endgroup$
    – Janne Kokkala
    Commented Mar 4, 2015 at 20:28
  • 1
    $\begingroup$ What is surprising to me is how close some rectangles get to the square. For example, according to OEIS A099390 extended, $20 \times 20$ gives almost $1.27 \times 10^{48}$ tilings while $16 \times 25$ gives just over $1.11\times 10^{48}$ tilings $\endgroup$
    – Henry
    Commented Mar 27, 2017 at 20:15
  • 1
    $\begingroup$ No. For instance you can make a large triangle with only one tiling, by taking the top half of an Aztec diamond. Such a shape has quadratic area as a function of its perimeter. You can also modify the construction to obtain any small number of tilings. By contrast a 2 x n rectangle has only linear area as a function of its perimeter, but it has exponentially many tilings (a Fibonacci number). $\endgroup$
    – Greg Kuperberg
    Commented May 25, 2018 at 14:39

1 Answer 1

Reset to default
9
$\begingroup$

Some answers are given in P. A. and L. Jordan, Enumeration of border strips and Weil-Peterson volumes. Journal of Integer Sequences, Vol. 22 (2019), Article 19.4.5.

We look at a certain type of regions (containing rectangles) parametrized by a binary word, and show that rectangles maximize the number of tilings. In contrast, all the shapes in the family admits the same number of border-strip tableaux, as in the Murnaghan-Nakayama rule. This partially answers question (3), and I would not be surprised if one can reduce the general question to this case. We also look at a natural $q$-analogue of tilings, that might be of interest.

Also, I think your question was in the back of my mind and partially inspired our paper.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ That's wonderful. I'm happy to think that I helped inspire your work here. $\endgroup$
    – Greg Kuperberg
    Commented Aug 29, 2019 at 20:05

You must log in to answer this question.

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