2. Graph Theory with Applications, J. A. Bondy and U. S. R. Murty (1976) -- out of print for a while, full text online. (Scanned, so it takes a while to load; you can also download it a chapter at a time.) From Anarchaia. (The same authors just finished a graduate text, to be published by Springer; read a blurb about it. I like the sound of the blurb. The book apparently also has a blog but the blog is empty.) Incidentally, I find it interesting that Springer's taxonomy of subdisciplines of mathematics includes "Number Theory and Combinatorics"; usually number theory seems to be classed with algebra.

Despite being an undergraduate book, the book includes a list of unsolved problems, which I think is a good practice; even if the intended reader is not expected to be able to solve these problems, it gives the interested student an idea of the sort of things that real mathematicians are interested in. (Of course, in some fields it wouldn't be practical to put such a list in a textbook; it needs to be possible for students to understand the statements of the problems.)

3. A combinatorial proof of the Rogers-Ramanujan and Schur identities, by Cilanne Boulet and Igor Pak. I haven't read it. (I came across it while looking for some other stuff on partitions.) The Rogers-Ramanujan identity is that the number of partitions of an integer n into parts that are congruent to 1 or 4 modulo 5 is equal to the number of partitions of n such that adjacent parts differ by at least 2.

For example, partitions of 12 counted by the first description are

11 + 1, 9 + 1 + 1 + 1, 6 + 6, 6 + 4 + 1 + 1, 6 + 1 + 1 + 1 + 1 + 1 + 1, 4 + 4 + 4, 4 + 4 + 1 + 1 + 1 + 1, 4 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

and by the second description,

11 + 1, 10 + 2, 9 + 3, 8 + 4, 8 + 3 + 1, 7 + 5, 7 + 4 + 1, 6 + 4 + 2

and there are eight in each list.

However, don't ask me which ones match up with which ones in the bijection! It's by no means obvious. This paper grabbed my interest because I knew there was no "nice" bijective proof, and the title led me to expect such a nice bijection. The authors lament:

Also, while our proof is mostly combinatorial it is by no means a direct bijection. The quest for a direct bijective proof is still under way, and as recently as this year Zeilberger lamented on the lack of such proof. The results in [23] seem to discourage any further work in this direction.

([23] is an in-preparation work of Pak, "Rogers-Ramanujan bijections are not geometric."; I'm kind of curious to see what it says.)

## 3 comments:

Pak defines Geometric Bijections in his paper "The Nature of Partition Bijections II". They are very cool.

David,

thanks for the tip!

Post a Comment