Type: Seminar

Distribution: World

Expiry: 18 May 2018

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

Auth: leo@121.212.38.163 (ltzo2369) in SMS-WASM

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.