[FOM] SHIFTING PARADIGMS?

[Timothy Y. Chow]

I wrote:

> As a first step, one could try to program computers to rediscover some 
> known celebrated bijections.

Someone asked me for more details about what I had in mind here.

If I were to embark on this project, I would start with Richard Stanley's 
list of different interpretations of the Catalan numbers.  This list 
provides an excellent cross-section of the different kinds of structures 
that arise in combinatorics.  One would have to come up with a good way to 
encode all these diverse structures and the various kinds of constructions 
on them that are used to define bijections.  This is non-trivial, but I 
think that if the project is to succeed at all, it needs to succeed at 
finding bijections between various interpretations of Catalan numbers.

Assuming success at the Catalan project, there are various directions one 
can go from there.  My personal favorite "elder brother" of the Catalan 
numbers is http://oeis.org/A001181 , the number of Baxter permutations of 
length n.  There aren't as many interpretations of these as there are of 
Catalan numbers, of course, but there are quite a few, and they are very 
different from each other, with the bijections being much harder than the 
Catalan bijections in several cases.  At the same time, they have a 
similar flavor to the Catalan numbers, so the work invested in the Catalan 
case should give one a leg up.  Success at the Baxter numbers would be a 
significant achievement in my opinion, especially if the computer were to 
turn up a new bijection (I think there are some pairs for which no direct 
bijection is currently known, other than by composing other bijections).

There are of course other famous bijections that one could try to recover. 
The Novelli-Pak-Stoyanovskii bijective proof of the hook-length formula 
comes to mind.  Currently I don't see how a computer could find this 
without, at minimum, huge hints to guide it towards constructing jeu de 
taquin.  In a similar vein, though probably slightly easier, is the 
Robinson-Schensted correspondence.  A bijective proof of the 
Rogers-Ramanujan identities would be another impressive benchmark.

Tim