NC State University

Department of Computer Science Colloquia Series 1998-99

Date: Thursday, October 29, 1998
Time: 3: 30 PM (refreshments), 4:00 PM (talk)
Place: Withers 402A, NCSU Historical Campus (click for courtesy parking request)

Speaker: Sylvie Corteel, Universite Paris-Sud, LRI, Orsay, France

The Bousquet-Conway Directed Animals

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.

Colloquia Home Page.