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

Abstract: 

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∈Za,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∈Nm∈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∈Za,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 D=⟨G,R,W⟩D=⟨G,R,W⟩ in which the finite graph GG is the primary part, the polynomial ring RR is the numerical part, and the set WW of weight functions assigns appropriate weights to sets of vertices.