Rhombus tilings with more than three directions

Question

The point of this question is to construct a list of references on the following subject: Fix vectors $v_1$, $v_2$, ..., $v_g$ in $\mathbb{R}^2$, all lying in a half plane in that cyclic order. I am interested in tilings by parallelograms of the form $\mathrm{Hull}(z, z+v_i, z+v_i+v_j, z+v_j)$. It is traditional in this subject to take all the $v_i$ of the same length, so that the tiles are rhombi. In my personal opinion, this convention is unmotivated, but I will obey convention and speak of rhombus tilings in the rest of this post.

The most obvious region to tile is a centrally symmetric $2g$-gon, with edges of the form $a_1 v_1$, $a_2 v_2$, ..., $a_g v_g$, $-a_1 v_1$, ..., $- a_g v_g$ for some positive integers $a_i$. One might also study tilings of the whole plane, perhaps with some periodicity conditions. I'm also open to hearing about results on regions of other shapes.

What I do want to do is rule out results which are special to the case $g=3$. Rhombus tilings of a centrally symmetric hexagon are in bijection with plane partitions, and hence all the tools of the plane partition literature are available. They are also related to perfect matchings of the hexagonal grid, so they can be studied by Kastelyn's method and related tools. They are also in bijection with certain families of non-crossing paths, so they can be studied by the Gessel-Viennot method. There is an embarrassment of tools available for the $g=3$ case. I want to limit this discussion only to tools that work for higher $g$.

Below the line is what I know so far:

---

$\bullet$ The two most obvious special cases are (1) tilings of an octagon where $(a_1, a_2, a_3, a_4) = (k,k,k,k)$ and (2) tilings of a $2g$-gon with $a_1=a_2=\cdots=a_g=1$. These are counted by Sloane A093937 and A006245 respectively. There is no closed formula in either case.

$\bullet$ Such rhombus tilings are in bijection with reduced words in $S_{a_1+a_2+\cdots+a_g}$ modulo commutation. In particular, the case where $a_1=a_2=\cdots=a_g=1$ corresponds to reduced words for the long word in $S_g$, modulo commutation. This has been rediscovered several times, but the canonical reference seems to be Rhombic tilings of polygons and classes of reduced words in Coxeter groups, by Serge Elnitsky.

$\bullet$ Drawing the paths dual to the rhombi gives us an arrangement of pseudo-lines, sometimes called deBruijn paths.

$\bullet$ Pseudo-line arrangements can be described by oriented matroids. Tracing through this language, the $a_1=a_2=\cdots=a_g=1$ case corresponds to rank $3$ oriented matroids $M$ on the set $\{ 1,2,\ldots, g, \infty \}$ such that the underlying matroid is uniform and $M/\infty$ is the uniform rank $2$ oriented matroid where $\{1,2,\ldots,g \}$ appear in that cyclic order. Call that rank $2$ matroid $U(g)$. Dualizing, we are looking for extensions of the rank $g-2$ oriented matroid $U(g)^{\ast}$ whose underlying matroid is uniform. One can generalize this description to the general case: The matroid $U(g)$ becomes the oriented matroid of rank $2$ made up of $g$ parallelism classes, of sizes $a_1$, ..., $a_g$, in that cyclic order.

Extensions of oriented matroids were studied by Sturmfels and Ziegler. In particular, they proved that a certain poset associated to this extension problem is homotopic to a sphere.

$\bullet$ Let $A$ and $B$ be two subsets of $\{ 1,2,\ldots, g \}$. We say that $A$ and $B$ are strongly separated if either every element of $A \setminus B$ is less than every element of $B \setminus A$, or is every element of $B \setminus A$ is less than every element of $A \setminus B$. A collection $\mathcal{C}$ of subsets of $\{ 1,2,\ldots, g \}$ is called strongly separated if every two elements in the collection are strongly separated. A collection is called maximally strongly separated if it is strongly separated and is not contained in any larger strongly separated collection.

Maximal strongly separated sets are in bijection with rhombus tilings of the $(1,1,\ldots,1)$-gon by a result of Leclerc and Zelevinsky. Although it doesn't appear to be in the literature, the generalization to other centrally symmetric polygons is easy enough: One uses the multiset with $a_i$ copies of $i$. Here if $A$ and $B$ are multisets which contain $u$ and $v$ copies of $i$, then $A \setminus B$ is the multiset which contains $\max(u-v, 0)$ copies of $i$.

$\bullet$ Any two rhombus tilings of the same $2g$-gon are linked by a sequence of flips, where a flip takes a single hexagon and retiles it. This is the same as the fact that any two reduced words are (up to commutation) joined by a sequence of braid moves.

$\bullet$ Take the flip graph referred to in the previous bullet point and direct it so that, in the language of braid moves, an edge points from $\cdots s_i s_{i+1} s_i \cdots$ to $\cdots s_{i+1} s_i s_{i+1} \cdots$. The resulting graph is acyclic, and is the Hasse diagram of the poset obtained by taking the transitive closure.

This poset is graded and has unique minimum and maximum elements. When $a_1=a_2=\cdots=a_g=1$, it is called the higher Bruhat order $B(g,2)$. It is a lattice for small $g$, but $B(6,2)$ is not a lattice.

$\bullet$ Let $1 \leq i < j < k \leq n$ and let $\gamma_i$, $\gamma_j$ and $\gamma_k$ be pseudolines in directions $(i,j,k)$. Then they either intersect each other in the order $(i,j)$, $(i,k)$, $(j,k)$, or the reverse of this order. A triple of such pseudo-lines is called a triangle. The triangle is ordinary if the intersections occur in the first manner, and inverted if the occur in the second.

For $\gamma$ and $\delta$ in $B(g,2)$, we have $\gamma \leq \delta$ if and only if every triangle which is inverted in $\gamma$ is also inverted in $\delta$. Presumably, this is also true when some of the sides of the polygon are longer than $1$, but I don't know a reference.

For $\gamma$ and $\delta$ two pseudo-line arrangements, the flip distance from $\gamma$ to $\delta$ is bounded below by the number of triangles which are inverted in one of $\gamma$ and $\delta$ but not the other. This lower bound is exact for $g=3$ or $4$, for $g=5$ if one of the $a_i$ is $1$, and for $(2,2,2,2,2)$, but not for any other case.

$\bullet$ The Bohne-Dress theorem: Let $C$ be the cube $\{ (x_1, \ldots, x_g) : 0 \leq x_i \leq a_i \} \subset \mathbb{R}^g$. Map $C$ to $\mathbb{R}^2$ by the linear map $\pi$ sending the $i$-th basis vector to $v_i$. So the $2g$-gon is the image of $\pi$. Then rhombus tilings of $\pi(C)$ are in bijection with continuous sections $\sigma: \pi(C) \to C$ whose image lies in the $2$-skeleton of the obvious cubical complex.

$\bullet$ Miscellaneous: some interesting lemmas about rhombus tilings are proved in my paper with Andre Henriques and in Shapiro-Shapiro-Vainshtein.

---

Some things I particularly don't know: Do we know the approximate number of these tilings? Can we sample uniformly from this set? Has anyone worked on periodic rhombus tilings? (Surely someone has, but I haven't found them.) What do random tilings of a large octagon look like? (Even if nothing is proven, someone presumably has a guess.) Is there a way of comparing elements of $B(g,2)$ in time less than order of $g^3$?

Answer 1

This post is almost ten years old, but I find it interesting and I would like to add a few pointers from my PhD, itself about 20 years old.

First, in the paper Integer Partitions, Tilings of 2D-gons and Lattices we explored the relations between rhombus tilings and integer partitions, and obtained a decomposition into disjoint distributive lattices of the flip graph of any 2D-gon tilings. In addition, the quotient of this set by these lattices has itself the same structure. These are direct consequences of the fact that they are isomorphic to generalized integer partitions.

Here is a simple example for the flip graph of an elemenraty octogon:

                         

Second, in the paper Graph encoding of 2D-gon tilings, we used the tile adjacency graph to process rhombus tilings and sample them, like the random decagon tiling below (the full resolution vector file is available on demand):

              

Answer 2

It's not entirely clear what question you're asking, but I think you are trying to collect other combinatorial objects that are in some sense equivalent to rhombus tilings. So here are 2 1/2, for the $a_i=1$ case:

• In the discrete geometry literature the "reduced words" that you cite to Elnitsky 1997 are known as circular sequences of permutations, and the standard citation is Goodman 1980. These are sequences of permutations, starting with 1 2 3 4 5 ... n and ending with n ... 5 4 3 2 1 such that each two consecutive permutations differ by swapping two adjacent values, and such that before the swap the two values are ordered lower then higher and after the swap they are in the reverse order.

• Wiring diagrams. These are a graphical representation of circular sequences from Goodman 1980 as a special kind of pseudoline arrangement in which one draws horizontal lines for the elements of the permutations, interrupted by crossings for each swap. Here's a figure, but it should have one more crossing between the middle two lines:

_{(source: eppstein at www.ics.uci.edu)}

• Sorting networks in which (as in bubble sort) comparisons happen only between adjacent values in the partially sorted sequence. You can turn a wiring diagram into a sorting network by replacing each crossing by a comparator.

Answer 3

Nicolas Destainville [arXiv:cond-mat/0101413] suggests that the "coupling from the past" algorithm can efficiently produce an exactly uniformly random rhombus tiling of any zonogon with integer side lengths.

There is no general formula because it is understood that the number isn't "round" (i.e., a product of small factors, especially one that potentially yields a $q$-analogue). However, it was discovered experimentally that the number of tilings of an $(a,b,1,1)$ octagon is round, and this was proven by Elnitsky in the reference that you cited.

An entropy model of the tilings, including the question of just approximating the number of tilings, is a really good question that I suspect is open. My evidence for this is that the general entropy study for hexagons is non-trivial even though it is solved. The full answer is that a random tiling has an inscribed Arctic ellipse with saturated entropy only in the very the center. I guess the first important paper on this ellipse is the one by Cohn, Larsen, and Propp [arXiv:math/9801059].

There is another interesting interpretation of these tilings (which you might already know). They are discrete minimal surfaces in the cubical lattice in $\mathbb{R}^g$. You can use this interpretation to prove that they are all connected by hexagon moves.

Finally, a pet peeve: The Kasteleyn method is not fundamentally different from the Gessel-Viennot method [arXiv:math/9810091]. There will never be a counting problem in which one method applies and some version of the other method does not. The matrices of the two methods are always equivalent in the sense of $K$-theory, i.e., up to integer changes of basis and stabilization.

Answer 4

Minor correction: the lower Hamming bound for $g=5$ if exact not only if one of the $a_i$ is 1, but also in the particular case where all the $a_i$ are equal to 2. Good synthesis of various results, by the way, thanx!

Also, on the problem of counting rhombus tilings for $d>3$ (for $d=3$ there are some beautiful results by Kenyon, Propp, Larsen, Cohn & Others), some partial results have been obtained by Nicolas Destainville (in particular in the $d=4$ case), see e.g.: Link