In 1991, David Gale and Raphael Robinson, building on explorations carried out by Michael Somos in the 1980s, introduced a three-parameter family of rational recurrence relations, each of which (with suitable initial conditions) appeared to give rise to a sequence of integers, even though a priori the recurrence might produce non-integral rational numbers. Throughout the '90s, proofs of integrality were known only for individual special cases. In the early '00s, Sergey Fomin and Andrei Zelevinsky proved Gale and Robinson's integrality conjecture. They actually proved much more, and in particular, that certain bivariate rational functions that generalize Gale-Robinson numbers are actually. | Porloet mannings for tho . Gale-Robinson sequences Mireille Bousquet-Melou CNRS LaBRI Bordeaux 1 s dc b Lib6ViO11 . Cedcx France . .JaTPropp University of Massachusetts Lowell MA 01854 USA Julian West 1 University of Victoria PO Box 3060 Victoria BO V8W3R4 Canada julian@ Submitted Jun 17 2009 Accepted Sep 25 2009 Published Oct 5 2009 Mathematics Subject Classification 05A15 05C70 . ------------------- . In 1991 Darud Gale and Raphael Robinson building on explorations arried out by Michael Somes i th 1980 intreduced a 1 ree-paramete farm y of rational recurrence relations each of which with suitable initial conditions appeared to give rise to a sequence 0 integers oven though a pno the recurrence might produce noil-integral rational numbers. Throughout the 90s proofs of integrality wore known. only for individual spoelal eases. In the early 00s Sergey Fomin and Andrei Zelevinsky proved Gale and Robinson s Integra lly eonjoeturo. They aetu-ally proved much mere and In par ieular that co tain bivariate rational functions hat generalize GaMobinso. numbers actually polynomials with integer 0 f-fielents However heir proof did not offer any enunerarive interpretation of the Gale-Robinson nnmbere polynomia s. Hero wo p Ovide such an mt rpretation in the setting of perfce matchings of graphs tvhi h makes hrtegrality pdyumnlallty obvi-ou. Moreover this interpretation implies hat the coefficients of the Gale-Robinson polynomials arc positive as Fomin and Zclcvinsky conjectured. JP was supported by grants from the National Security Agency and the National Science Foundation. 1JW was supported by the National Sciences and Engineering Research Council of Canada. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R125 1 . . . Linear rccurrcn CCS are ubrqurtou in combinatorics. as part of a broad gene al f amework that is well-studied and well-understood in particular many combmatorrally-c H cd
