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).

4more comments