Perfect matchings for the three-term Gale-Robinson sequencesReport as inadecuate

Perfect matchings for the three-term Gale-Robinson sequences - Download this document for free, or read online. Document in PDF available to download.

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique 2 Dept. of Mathematics, University of Massachusetts Lowell 3 Dept. of Mathematics, University of Victoria

Abstract : 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 polynomials with integer coefficients. However, their proof did not offer any enumerative interpretation of the Gale-Robinson numbers-polynomials. Here we provide such an interpretation in the setting of perfect matchings of graphs, which makes integrality-polynomiality obvious. Moreover, this interpretation implies that the coefficients of the Gale-Robinson polynomials are positive, as Fomin and Zelevinsky conjectured.

Mots-clés : Perfect matchings Gale-Robinson sequences

Author: Mireille Bousquet-Mélou - James Propp - Julian West -



Related documents