Lecture by Günter Rote (Freie Universität Berlin): Lattice paths with states, and counting geometric objects via production matrices

Nov 04, 2019 | 02:15 PM

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. There are strong indications that, under some natural technical conditions, the number of such paths is asymptotic to C^n/(√n^3), for some "growth constant" C which I will show how to compute.

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 were recently formulated in terms of so-called production matrices.

This is ongoing joint work with Andrei Asinowski and Alexander Pilz.

Time & Location

Nov 04, 2019 | 02:15 PM

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)