A. Mani and R. Stones in their paper from 2016 (SIAM-Journal of Discrete Mathematics) study the sequence of integers $tc_{a,b}(n) = T(K_n,a,b)$, where $T(G,X,Y)$ is the Tutte polynomial and $a,b \in \Z$. For the case $a=1$ this gives a sequence $C(n,b)$ which for $b=2$ counts the number of labeled connected graphs of order $n$.

They give a description of the modular behavior of $C(n,b)$ modulo prime powers $p^k$ for $b \neq 1 \mod{p}$. Their tools for the analysis of the modular behaviour of $C(n,b)$ are elementary number theory and group actions. Similar methods have been employed in 1981 by C. Blatter and E. Specker using additionally tools from logic to analyze the modular of a very large class of combinatorial counting functions. In fact it follows from their work that the sequence $C(n,2)$ is ultimately periodic modulo every $m \in \N$.

A. Mani and R. Stone also formulate a conjecture concerning the modular behavior of $tc(n,a,b)$. In this talk we study the modular behaviour of $tc(n,a,b)$, for $a,b \in \Z$ and a modulus $m$ and prove a modified form of their conjecture. Technically, we show that evaluations of the Tutte polynomial are evaluations of suitably chosen MSOL-polynomials and apply the Specker-Blatter theorem. We also study the modular behaviour of $P(K_n,a,b)$ for the class of MSOL-polynomials. Our main technical contribution consists in showing how the Specker-Blatter can be applied in this new context.

The model theory of MSOL polynomials is metafinite model theory. An MSOL-polynomial as used in this talk can be defined in terms of a metafinite structure $\mathcal{D}=\left\langle G,\mathcal{R},\mathcal{W} \right\rangle$ in which the finite graph $G$ is the primary part, the polynomial ring $\mathcal{R}$ is the numerical part, and the set $\mathcal{W}$ of weight functions assigns appropriate weights to sets of vertices.