[FOM] SHIFTING PARADIGMS?
Timothy Y. Chow
tchow at alum.mit.edu
Wed Jul 30 23:40:56 EDT 2014
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
More information about the FOM
mailing list