# Lattice Paths with States, and Counting Geometric Objects via Production Matrices

## Günter Rote, Institution: Freie Universität Berlin

## Date and time: 2pm, Thursday, December 27, 2018

## Place: CUNY Graduate Center, Rm 4419

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 $q_0$ to the point $(n,0)$ without going below the x-axis. Under some
natural technical conditions, I conjecture that the number of such
paths is asymptotic to $C^n/\sqrt(n^3)$, and I will show how to compute
$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 were recently formulated in
terms of so-called production matrices.

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