##
Integer Sequences Arising from Graph Polynomials:

An Application of a Theorem by C. Blatter and E. Specker

###
Tomer Kotek

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.