Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?


A subset S of the xy-plane is star-convex if there is a point s in S such that the line segment [st] is contained in S for every t in S. For example the Young diagram of a partition is star convex with s taken as the origin.

A sublattice G of the plane is a bipartite graph whose vertices are some points in the plane with integer coordinates. Two vertices in G whose x-coordinates differ by 1 or whose y-coordinates differ by 1 are joined by an edge.

A tiling of a graph by dominos (dimer covering or perfect matching) is a collection of edges such that every vertex belongs to exactly one edge in the tiling.

Motivating example:

For $n\geq1$ there is a bijection between the Young diagrams of $2n$ which have a unique tiling by dominos and two copies of the set of partitions of $n$.

We see this as follows:

Represent the partition of $2n$ using beads on a $2$-runner abacus (as explained in James & Kerber's book The Representation Theory of the Symmetric Group). Moving a bead on a runner into a space immediately above it on the abacus correspond to the removal of a domino (2 adjacent boxes) from the diagram.

The Young diagram has a tiling by dominos if and only if there are an equal number of beads on each runner (the partition has an empty 2-core). The tiling is unique if one runner is the bead sequence of a partition of $n$ and the other runner represents the empty partition.

Specific Examples:

For $2n=2,4,6$ only the hook partitions $[k,1^{2n-k}]$ have a unique tiling by dominos. In addition to the $8$ hook partitions of $2n=8$, the partitions $[4,3,1]$ and $[3,2^2,1]$ have unique tilings. These correspond to the partition $[2^2]$ of $n=4$.

  • $\begingroup$ Would you mind including a definition of "star convex" and "n-vertex sublattice"? $\endgroup$ Nov 9, 2013 at 6:44
  • $\begingroup$ I think that for you it is clear what you are asking but for most of us it is not. So is a sublattice a finite set of points? Then how could it be star-convex? My guess would be that you mean polyominoes that have a diamond-like shape, so they look like four (rotated) Young-diagrams glued together at their origins. $\endgroup$
    – domotorp
    Nov 18, 2013 at 19:06
  • $\begingroup$ Dear Domotorp, apologies for the imprecision in my description. Here is what I mean. The usual definition of the Young diagram of a partition is as a collection of square boxes in the plane. A Young diagram is star-convex because the origin sees all points. You are correct that I mean a polyomino which has a diamond like shape, but there won't be a predefined origin - as in the case of a Young diagram. The dominos are 2x1 or 1x2 sets of squares. A young diagram can also be interpreted as a bipartite graph with vertices the squares, and the edges joining squares that share an edge. $\endgroup$ Nov 22, 2013 at 9:34
  • $\begingroup$ Hi @JohnMurray, perhaps you interested by other domino tiling problems $\endgroup$ Apr 11, 2020 at 4:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.