[FOM] Computer searches for combinatorial bijections
carette at mcmaster.ca
Wed Oct 11 16:14:03 EDT 2006
Timothy Y. Chow describes work of Zeilberger which involves,
> The examples described by Zeilberger still require the programmer to
> create data structures and algorithms that are highly specific to the
> particular pair of combinatorial objects in question. But ideally, one
> would like to create a general environment with a language that is
> flexible enough to allow the description of a wide variety of
> combinatorial objects. The user would then describe two classes of
> combinatorial objects in this formal language, and the program would then
> go off in search of a bijection between the two, returning with a
> description of a bijection and a proof that it is correct.
and then asks
> The question I have is, is there any existing environment or language that
> might be adaptable to such a project?
Yes, there is. First, the proper mathematical framework to do this in
is indeed that of *species*, as you mention. A very readable account is
a book by Bergeron, Labelle and Leroux, see
http://bergeron.math.uqam.ca/Species/especes.html. They make the theory
very practical and down-to-earth (unlike some accounts).
One can get a taste of the theory at
http://en.wikipedia.org/wiki/Combinatorial_species (which contains
Part of the theory of species for combinatorial structures has been
implemented in the Maple package 'combstruct' (short for combinatorial
structures). See http://algo.inria.fr/libraries/autocomb/ for some
examples of its use.
Note that combstruct can at least help you prove some basic things about
your combinatorial structures -- for example you can often show that two
structures' generating functions are equal. This is certainly a
necessary, but unfortunately not sufficient, condition for two
structures to be equal.
The framework of species gives one a lot of canonical maps and tools
between species, which help tremendously in the automation of possible
bijections. The aforementioned book is filled with further insights.
The approach I would take would be based on so-called 'combinatorial
differential equations', in exactly the same way the WZ-method uses
recurrences for proving combinatorial identities. The real trick would
be to find a way to unwind such equations into an english description of
a bijection -- that I don't have a handle on right now.
More information about the FOM