OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT

We say that a finite algebra 𝔸 = 〈A; F〉 has the ability to count if there are subalgebras C of 𝔸 3 and Z of 𝔸 such that the structure 〈A; C, Z〉 has the ability to count in the sense of Feder and Vardi. We show that for a core relational structure A the following conditions are equivalent: (i) the variety generated by the algebra 𝔸 associated to A contains an algebra with the ability to count; (ii) 𝔸 2 has the ability to count; (iii) the variety generated by 𝔸 admits the unary or affine type. As a consequence, for CSP's of finite signature, the bounded width conjectures stated in Feder–Vardi [10], Larose–Zádori [17] and Bulatov [5] are identical.