Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Can anyone suggest a simple and efficient way (preferably embodied in computer code) to compute the average height function for lozenge tilings of an $a,b,c,a,b,c$ semiregular hexagon? I prefer to scale my height functions so that the height-change along each tile-edge is 1 and so that the lowest possible height of any vertex in any tiling of the region is 0, so that for instance when $a=b=c=1$ the average height function alternates between 1 and 2 on the boundary and is 3/2 in the middle.

When we replace the tiling model by the (dual) dimer model, height becomes associated with faces rather than vertices, and the average height of a face can be written as a linear combination of edge-inclusion probabilities (for the uniform distribution on dimer configurations); each of these probabilities can be written as a ratio of determinants, so I do know one way to compute the average height functions I'm interested in.

But I'm hoping for something simpler, along the lines of the recurrence formulas that apply to domino tilings of Aztec diamonds. Perhaps something like this follows from the recent work of Borodin (or maybe from the earlier work of Kuperberg), or can be obtained from Kuo's graphical condensation method. (And have I mentioned Speyer's paper on the octahedron recurrence? Ah, I just did.)

share|improve this question

1 Answer 1

up vote 5 down vote accepted

David Speyer made a blog post a while back saying how to do this:


It wasn't the main point of the blog post, but he does say how to use Kuo's graphical condensation method to compute such things. In short, if $H(a,b,c)$ is the set of perfect matchings on your hexagon, you're supposed to think of Kuo's beautiful technique as a bijection between the sets

$H(a,b,c) \times H(a-1,b-1,c)$


$[H(a-1,b,c) \times H(a,b-1,c)] \cup [H(a,b,c-1) \times H(a-1,b-1,c+1)] $

If you're interested in the expected value of some statistic on $H(a,b,c)$ --- he was talking about edge-placement probabilities, but I don't see why it wouldn't work for the height function at a given face --- you should compute this expectation on both sides of Kuo's bijection. In general that'd be tricky, but for the hexagon, it's quite tractable to do, since you know the sizes of all of these sets explicitly. For instance, MacMahon gave a closed formula for $H(a,b,c)$, which can also be found in Kuo's paper; Speyer even works out the relative sizes in his post for you. This gives you a recursive answer to your question, by dividing through by the term which came from the expected height function of $H(a-1,b-1,c)$. The base case is where one of a,b, or c is zero, which is easy.

That's not code, obviously. Sorry! I'm rather busy travelling over the next few weeks, but I can try to do it in January sometime. If I forget, and nobody else does it, please remind me.

share|improve this answer
Thanks! This is a good enough answer for now. I wanted a quick way to compute average height functions so I could explore a certain conjecture of mine (too recondite to explain here), but I discovered that my conjecture is false, so my original motivation for wanting to compute average height functions is now gone. (It's possible that someday I'll find an improved version of the conjecture that appears to be true, at which point I might once again want to know a good way to compute average height-functions, but for the time being, it's not something I need.) –  James Propp Dec 31 '11 at 17:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.