Gunter Rote:
Lattice paths with states, and counting geometric objects via
production matrices

Abstract:

We consider paths in the plane governed by the following rules:

(a) There is a finite set of states.
(b) For each state q, there is a finite set S(q) of
     allowable "steps" ((i,j),q'). This means that from any
     point (x,y) in state q, we can move to (x+i,y+j) in state q'.

We want to count the number of paths that go from (0,0) in some starting
state q0 to the point (n,0) without ever going below the x-axis.
Under some natural technical conditions, I conjecture that the number of
these paths is asymptotically equal to C^n/ root n^3, and I will show
how to compute the growth constant C.

I will discuss how lattice paths with states can be used to model
asymptotic counting problems for some non-crossing geometric
structures (such as trees, matchings, triangulations) on certain
structured point sets. These problems come up in extremal constructions
in discrete geometry, and they have been formulated in
terms of so-called production matrices.

This has been ongoing joint work with Andrei Asinowski and Alexander Pilz.