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$?

simplepseudoline arrangements (where at most two pseudolines meet at any crossing) are the ones dual to rhombus tilings. For non-simple arrangements you get tilings by centrally symmetric polygons that may not themselves be rhombs. And for weak pseudoline arrangements (where the pseudolines that don't cross don't have to form parallel bundles, e.g. like lines in the hyperbolic plane) you still get tilings by centrally symmetric polygons, but of a region that is not necessarily convex — for this last bit, see e.g. my paper arXiv:cs/0406020. $\endgroup$ – David Eppstein Oct 17 '11 at 16:03