Abstract
Tame congruence theory identifies six Maltsev conditions associated with locally finite varieties omitting certain types of local behaviour. Extending a result of Siggers, we show that of these six Maltsev conditions only two of them are equivalent to strong Maltsev conditions for locally finite varieties. Besides omitting the unary type, the only other of these conditions that is strong is that of omitting the unary and affine types.
We also provide novel presentations of some of the above Maltsev conditions.
Similar content being viewed by others
References
Barto, L.: The collapse of the bounded width hierarchy. J. Logic Comput., to appear
Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 595–603. IEEE Computer Soc., Los Alamitos, CA (2009)
Barto, L., Kozik, M.: Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Log. Methods Comput. Sci. 8(1), 1:07, 27 (2012)
Barto, L., Kozik, M.: Constraint satisfaction problems solvable by local consistency methods. J. ACM 61(1), 3:1–3:19 (2014)
Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38(5), 1782–1802 (2008/09)
Barto, L., Kozik, M., Stanovský, D.: Mal’tsev conditions, lack of absorption, and solvability. Algebra Universalis, to appear (2014)
Bergman, C.: Universal Algebra, Fundamentals and Selected Topics. Pure and Applied Mathematics (Boca Raton), vol. 301. CRC Press, Boca Raton (2012)
Bulatov, A.A.: Bounded relational width (2009, preprint)
Bulatov, A.A., Valeriote, M.: Recent results on the algebraic approach to the CSP. In: Creignou et al. [11]., pp. 68–92
Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78. Springer, New York (1981)
Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.): Complexity of Constraints – An Overview of Current Research Themes Result of a Dagstuhl Seminar., Lecture Notes in Computer Science, vol. 5250. Springer (2008)
Freese, R., McKenzie, R.: Maltsev families of varieties closed under join or Maltsev product (2013 preprint)
García, O.C., Taylor, W.: The lattice of interpretability types of varieties. Mem. Amer. Math. Soc. 50 (305) (1984)
Hagemann, J., Mitschke, A.: On n-permutable congruences. Algebra Universalis 3, 8–12 (1973)
Hobby, D., McKenzie, R.: The structure of finite algebras, Contemporary Mathematics vol. 76. American Mathematical Society, Providence (1988). Revised edition (1996)
Jónsson, B.: Algebras whose congruence lattices are distributive. Math. Scand. 21 (1967), 110–121 (1968)
Kearnes, K.A., Kiss, E.W.: The shape of congruence lattices. Mem. Amer. Math. Soc. 222 (1046) (2013)
Kearnes K., Marković P., McKenzie R.: Optimal strong Mal’cev conditions for omitting type 1 in locally finite varieties. Algebra Universalis 72, 91–100 (2014)
Kearnes K.A., Szendrei Á.: Clones of algebras with parallelogram terms. Internat. J. Algebra Comput. 22(1), 1250005 (2012)
Mal′cev A.I.: On the general theory of algebraic systems. Mat. Sb. N.S. 35(77), 3–20 (1954)
Maróti M., McKenzie R.: Existence theorems for weakly symmetric operations. Algebra Universalis 59, 463–489 (2008)
McKenzie, R.N., McNulty, G.F., Taylor, W.F.: Algebras, lattices, varieties. Vol. I. The Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey (1987)
Nešetřil, J., Siggers, M.: Combinatorial proof that subprojective constraint satisfaction problems are NP-complete. In: Mathematical foundations of computer science 2007, Lecture Notes in Comput. Sci., vol. 4708, pp. 159–170. Springer, Berlin (2007)
Siggers M.H.: A strong Mal’cev condition for locally finite varieties omitting the unary type. Algebra Universalis 64, 15–20 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by R. Freese.
The first author was supported by National Science Centre DEC-2011/01/B/ST6/01006. The third and fourth authors were supported by the Natural Sciences and Engineering Research Council of Canada.
Rights and permissions
About this article
Cite this article
Kozik, M., Krokhin, A., Valeriote, M. et al. Characterizations of several Maltsev conditions. Algebra Univers. 73, 205–224 (2015). https://doi.org/10.1007/s00012-015-0327-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00012-015-0327-2