The Specker-Blatter Theorem Revisited

摘要

In this paper we study the generating function of classes of graphs and hypergraphs modulo a fixed natural number m. For a class of labeled graphs C we denote by fc(n) the number of structures of size n. For C definable in Monadic Second Order Logic MSOL with unary and binary relation symbols only, E. Specker and C. Blatter showed in 1981 that for every m ∈ N, fc(n) satisfies a linear recurrence relation fc(n) = sum from j=1 to dm of a_j~((m))fc(n-j), over Z_m, and hence is ultimately periodic for each m. In this paper we show how the Specker-Blatter Theorem depends on the choice of constants and relations allowed in the definition of C. Among the main results we have the following: -For n-ary relations of degree at most d, where each element a is related to at most d other elements by any of the relations, a linear recurrence relation holds, irrespective of the arity of the relations involved. -In all the results MSOL can be replaced by CMSOL, Monadic Second Order Logic with (modular) Counting. This covers many new cases, for which such a recurrence relation was not known before.