51
$\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).

$\endgroup$
  • 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 Apr 1 '14 at 10:48
  • 2
    $\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 Nov 20 '14 at 22:29
  • $\begingroup$ I've looked a "local optima", i.e., sets of squares whose number of tilings is larger than any set of squares obtained by moving one or two squares. For small $N$ only the global optimum is a local optimum, but for 6 dominoes, the (two possible) configuration(s) made by gluing a 2×2 square to the long side of a 2×4 rectangle are local optima with 12 tilings (compared to the 13 tilings of 3×4). This suggests that a local approach would not work so well. $\endgroup$ – Bruno Le Floch Nov 21 '14 at 20:40
  • 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 Mar 4 '15 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 Mar 27 '17 at 20:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.