The University of Michigan Combinatorics Seminar
Winter 2001
February 2, 4:10-5:00, 4088 East Hall

Somos sequences and bilinear combinatorics

Jim Propp

University of Wisconsin


Linear recurrences (and, with them, ordinary generating functions) are ubiquitous in combinatorics, as part of a broad general framework that is well-studied and well-understood; in contrast, bilinear recurrences such as

sn+4 = (sn+1sn+3 + sn+22) / sn
are encountered far less often, and these encounters tend to be viewed in isolation from one another.

In this talk I will describe some types of combinatorial objects whose properties make them well-suited to a (nascent) general theory of bilinear recurrence relations. In some interesting cases (e.g., the Somos-4 recurrence given above), algebra is one step ahead of combinatorics, and we are temporarily in the unusual position of being able to enumerate combinatorial objects for which we lack a combinatorial description!

I will attempt to convince members of the audience that some basic problems connected with bilinear recurrence relations are compelling and accessible. If I succeed at this, I hope to recruit new members for an email forum started last fall that is jointly exploring these problems.

(Most of the lecture will be accessible to advanced undergraduates.)