Modul:   MAT591  Discrete mathematics

Necktie knots, grammars, generating functions and Cayley graph growth

Vortrag von Dr. Mikael Vejdemo-Johansson

Sprecher eingeladen von: Prof. Dr. Rémi Abgrall

Datum: 17.05.16  Zeit: 11.15 - 12.15  Raum: Y27H28

Generating functions are a standard and powerful technique in combinatorics, translating counting tasks to algebra and analysis of power series. One recently emerged area of application is to count strings in a formal language: a grammar for a context-free language produces functional equations for parts of the language — solving the corresponding system of equations produces a rational function expression for the generating function of the grammar.

We applied these techniques to count necktie knots in a paper, published in 2015, and have since found applications to group theory: specifically, for automatic groups, a grammar exhibiting the automatic structure can be used to describe the Cayley graph, and by counting strings in the grammar by their string lengths, a generating function for the size of the Cayley graph — a growth function of the group — can be computed.

This way we can recover existing results on the growth functions of braid groups, and extend these results for cases, such as the braid groups, where the automatic structure is built from other sets of generators than the ones that might be naively picked for the group structure.