For all relational signatures $\sigma$ and nonnegative integers $n$, I want to count the number of isomorphism types of structures of order $n$ of the signature $\sigma$.

What I mean by structure is a pair $\mathfrak{A}=(A,( R(\mathfrak{A})_{R\in\sigma} )) $ for some relational signature $\sigma$ of predicates of arity $\geq 1$ and some finite set A. I think, I figured it out for the case when all predicates in $\sigma$ have arity $1$. Say, it is $\mathfrak{A}=(A, P_1(\mathfrak{A}),\ldots,P_m(\mathfrak{A}) ) $ for some nonnegative integer $m$. Then each vertex is coloured in certain ways: It could be that it is in $ P_1(\mathfrak{A}),P_2(\mathfrak{A}) $ but not in $P_3(\mathfrak{A})$ (for $m=3$); so we can assign to each vertex a subset of all colours it possesses. Then two structures of this signature are isomorphic if and only if for each subset of $\sigma=\{P_1,\ldots,P_m\}$, there are exactly the same number of vertices coloured this way in both structures.

But there are exactly $2^m$ subsets of the above $\sigma$, and so what we look for is the number of all $2^m$-tuples $ (a_1,\ldots,a_{2^m}) $ s.t. $\sum_{i\in [1,2^m]}a_i = n $ where n is the order of structures we want to compute the number of isomorphism types for. Well and this is a simple combinatorial fact this number is equal to $ \binom{n+2^m-1}{n} $.

I want to do the same thing without the restriction that $\sigma$ only contains predicates of arity $1$. I would be glad about ideas how to do this for structures of a signature with exactly one $r$-ary predicate for some arity $r\geq 2$, and also about ideas how to combine the numbers of isomorphism types of two such signatures (for some fixed $n$).

  • $\begingroup$ You can do something similar with padding. A relation of arity k is just a subset of A^k. So you can pad a relation of smaller arity up to one of arity k by allowing the later places to range over all elements. Now you get a weak upper bound for an arbitrary signature, and a similar bound when all the relations have the same arity. Gerhard "Goes For Easy Cases First" Paseman, 2017.08.04. $\endgroup$ Aug 5, 2017 at 0:14
  • $\begingroup$ There is not going to be anything resembling a simple list of invariants, as in the unary case. You may be able to cook up something with the Pólya enumeration theorem. $\endgroup$ Aug 5, 2017 at 11:24
  • $\begingroup$ So is giving lower and upper bounds all I can do here? Ok, this Polya enumeration theorem looks promising... $\endgroup$
    – D. Rusin
    Aug 5, 2017 at 15:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.