Joint Colloquium: Makowsky -- Integer Sequences Arising from Graph Polynomials: An Application of a Theorem by C. Blatter and E. Specker

A.  Mani and R.  Stones in their paper from 2016 study the sequence of integers
tca,b(n)=T(Kn,a,b)tca,b(n)=T(Kn,a,b), where T(G,X,Y)T(G,X,Y) is the Tutte polynomial and
a,b∈ℤa,b∈Z.  For the case a=1a=1 this gives a sequence C(n,b)C(n,b) which for
b=2b=2 counts the number of labeled connected graphs of order nn.  They give a
description of the modular behavior of C(n,b)C(n,b) modulo prime powers pkpk for
b≠1modpb≠1modp.  Their tools for the analysis of the modular behaviour of
C(n,b)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 avery large class of combinatorial counting functions.  In fact
it follows from their work that the sequence C(n,2)C(n,2) is ultimately periodic modulo
every m∈ℕm∈N.  A.  Mani and R.  Stone also formulate a conjecture concerning the
modular behavior of tc(n,a,b)tc(n,a,b).  In this talk we study the modular behaviour of
tc(n,a,b)tc(n,a,b), for a,b∈ℤa,b∈Z and a modulus mm 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(Kn,a,b)P(Kn,a,b) for the class of
MSOL-polynomials.  Our main technical contribution consists in showing how the
Specker-Blatter can be applied inthis new context.  The model theory of MSOL polynomials
is metafinite model theory.  AnMSOL-polynomial as used in this talk can be defined in
terms of a metafinite structure =⟨G,,⟩D=⟨G,R,W⟩ in which the finite
graph GG is the primary part, the polynomial ring R is the numerical part, and the
set W of weight functions assigns appropriate weights to sets of vertices.  Joint
work with Tomer Kotek.