Logical Structures in Computation Seminar

An Application of the Specker-Blatter Theorem to Graph Polynomials

In 1981 C. Blatter and E. Specker gave an application of logic to combinatorics dealing with modular periodicity of combinatorial sequences. This arguably was the first statement of a "meta-theorem" in finite model theory. It states that combinatorial sequences (counting functions) definable in Monadic Second Order Logic are ultimately periodic modulo every integer $m$. In this talk we discuss further developments concerning this theorem and give new applications to graph polynomials. In particular we prove a conjecture by A. Mani and R. Stones from 2016.
Joint work with T. Kotek (Technical University, Vienna, Austria)