Speaker: Sylvie Corteel, Universite Paris-Sud, LRI, Orsay, France
Abstract:
A {\em directed animal} $A$ is a finite set of vertices on an
acyclic infinite periodic lattice $L$ such that any vertex of $A$ can
be reached from a distinguished vertex, called the source, through an
oriented path of $L$ having all its vertices in $A$. Animals are
defined up to a translation on the lattice. Bousquet-Melou and Conway
found algebraic equations for the area generating function of directed
animals on an infinite family of regular, non-planar, two-dimensional
lattices by using equivalences with hard particle models (statistical
physics techniques.) We give in this paper a bijective proof of their
results which is a generalization of Viennot's heaps of pieces. Thanks
to this proof we can get some exact enumeration formulas for the number
of configurations with $n$ vertices which could not be deduced directly
from the algebraic equation and did not appear in earlier work. Moreover,
we give an extension of these results to another infinite family
of regular, non-planar, two-dimensional lattices.
This represents joint work with Alain Denise and Dominique
Gouyou-Beauchamps at LRI, Orsay.
Short Bio: Sylvie Corteel received her undergraduate degree in Computer Science at Compiegne and her M.S. in Computer Science from N.C. State in May 1997. She is currently working on her Ph.D. thesis at the Universite Paris-Sud, Laboratoire de Recherche en Informatique (LRI) in Orsay, France. Her research interests are in combinatorics and combinatorial computing and to date she is co-author of four journal articles and two conference papers in these areas.