Ash's counting functions and characterization of Ehrenfeucht-Fra\"iss\'e
equivalence for two classes of finite graphs


Abstract:

Ash's functions $N_{\sigma,k}$ count the number of $k$-equivalence
classes of $\sigma$-structures of size $n$. Some conditions on their
asymptotic behavior imply the long standing spectrum conjecture. We
present a new condition which is equivalent to this conjecture
and we discriminate some easy and difficult particular cases.
We present a complete analysis of Ehrenfeucht-Fra\"{\i}ss\'e equivalence
in two classes of finite graphs, in connection with the difficult cases.
We deduce that the corresponding Ash counting functions are eventually
periodic and exhibit a natural counterexample to Ash's constant conjecture.