Fimmta málstofa haustsins verður föstudaginn 14. október kl 10:30 í Naustinu, húsi Endurmenntunar. Fyrirlesari er Anders Karl Claeson, Háskóla Íslands.
Titill hans er The Goulden-Jackson cluster method. Anders mun halda áfram með sama efni föstudaginn 21. október.
Abstract. We consider the problem of calculating the number of strings of length n (over a fixed alphabet) that do not contain a given (shorter) string as a factor/pattern. In a celebrated paper from 1981 Guibas and Odlyzko gave an answer in the form of a simple rational generating function that only depends on the so called autocorrelation polynomial of the pattern. We will review this theorem as well as a more general method due to Goulden and Jackson. We shall also consider applications to so called nontransitive games.
This is the first of two talks. The first talk is meant to be elementary and approachable. It contains no results by the speaker and it serves the dual purpose of introducing some classical results in combinatorics and setting the stage for the second talk, which will contain results by the speaker. The aim is to make the second talk understandable on its own, but easier to understand with the background given in the first talk.