Abstract
We show that a finite algebra has a Taylor operation if and only if it has an operation satisfying a particular set of 6-ary Taylor identities. As a consequence we get the first strong Mal’cev condition for the family of locally finite varieties omitting the unary type. This is of interest to combinatorialists, as it is conjectured that a Constraint Satisfaction Problem defined by a core relational structure is polynomial time solvable exactly when a certain associated variety omits the unary type. Our result implies that the problem of deciding if a core relational structure meets this characterisation is itself in NP.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barto L., Kozik M., Niven T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to the conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38, 1782–1802 (2008/09)
Berman J., Idziak P., Marković P., McKenzie R., Valeriote M., Willard R.: Varieties with few subalgebras of powers. Trans. Amer. Math. Soc. 362, 1445–1473 (2010)
Bulatov A.: H-coloring dichotomy revisited. Theoret. Comput. Sci. 349, 31–39 (2005)
Bulatov, A., Jeavons, P.: Algebraic structures in combinatorial problems. Tech. Rep. MATH-AL-4-2001, Technische universitt Dresden, Dresden, Germany
Bulatov A., Jeavons P., Krokhin A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720–742 (2005)
Feder T., Vardi M.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28, 57–104 (1999). doi:10.1137/S0097539794266766
Hell P., Nešetřil J.: On the complexity of H-colouring. J. Combin. Theory B 48, 92–100 (1990)
Hobby, D., McKenzie, R.: The Structure of Finite Algebras. Contemporary Mathematics, vol. 76. American Mathematical Society, Providence (1988)
Jeavons P.G.: On the algebraic structure of combinatorial problems. Theoret. Comput. Sci. 200, 185–204 (1998). doi:10.1016/S0304-3975(97)00230-2
Larose B.: Taylor operations on finite reflexive structures. Int. J. Math. Comput. Sci. 1, 1–26 (2006)
Markovič, P.: Personal communication
Maróti M., McKenzie R.: Existence theorems for weakly symmetric operations. Algebra Universalis 59, 463–489 (2008). doi:10.1007/s00012-008-2122-9
McKenzie, R.: Personal communication
Nešetřil J., Siggers M., Zadori L.: A combinatorial CSP dichotomy classification conjecture. European Journal of Combinatorics 31, 280–296 (2010)
Taylor W.: Varieties obeying homotopy laws. Canad. J. Math. 29, 498–527 (1977)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by M. Valeriote.
This work was supported by Kyungpook National University Research Fund.
Rights and permissions
About this article
Cite this article
Siggers, M.H. A strong Mal’cev condition for locally finite varieties omitting the unary type. Algebra Univers. 64, 15–20 (2010). https://doi.org/10.1007/s00012-010-0082-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00012-010-0082-3