Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, November 13, 2007 - 4:00pm

Mireille Bousquet-Melou

CNRS, LaBRI, University of Bordeaux I

Location

University of Pennsylvania

4N30

A walk on the square lattice is self-avoiding (SA) if it never visits twice the same vertex. The enumeration of these walks is notoriously difficult, though intriguing conjectures exist on the asymptotic behaviour of the corresponding numbers. Many authors have considered restricted, more tractable families of SAW. For instance directed SAW (formed of North and East steps), or even partially directed SAW (formed of N, E and W steps) can easily be counted. Both classes are found to have a rational generating function. Several authors have independently introduced a natural class of SAW, called prudent SAW, that includes the above two classes. A prudent SAW is obtained from a shorter one by adding a new step in such a way this step can be repeated any number of times without hitting an already visited point. Four families of prudent SAW, of increasing generality, can be defined in a natural way: the first class is the class of partially directed walks, counted by a rational gen. fun. The second class was shown by Duchi to have an algebraic gen. fun. Here, we enumerate walks of the third class, and prove that their gen. fun. is not D-finite (in particular, not algebraic). The fourth class is that of all PDAW: we give a functional equation for their gen.fun., which we have not solved at the moment. However, the latter equation suggests to consider an analogous model of prudent SAW on the triangular lattice, which we can solve exactly: again, the gen. fun. is shown to be non-D-finite.