Perfect Matchings for the Gale-Robinson

Sequence

 

Julian West ^[1]

Malaspina University-College, British Columbia, Canada

westj@mala.bc.ca

 

Abstract.      Full Text PDF

 

A domino is a rectangle of dimensions 1 by 2. An “Aztec diamond" of order  is a diamond-shape array of squares with height and width . The number of different ways of covering an Aztec diamond of order n with dominos is . (Alternatively this can be viewed as the number of perfect matchings in the dual graph.) There are a number of attractive proofs of this formula, notably the “condensation" proof used by Eric Kuo to verify the recursion formula. We will generalize this proof to the “Gale-Robinson" recurrences, which have the form ,   where . (The Aztec diamond recurrence corresponds to the case of .) In the process, we construct graphs analogous to the Aztec diamonds and in which the number of perfect matchings are given by the appropriate term in the Gale-Robinson sequence.