A strong Mal'cev condition for locally finite varieties omitting the unary type
type: Item
instance of: scholarly article
title: A strong Mal'cev condition for locally finite varieties omitting the unary type
zbMATH Open document ID: 1216.08002
published in: Algebra Universalis
publication date: 2011-01-07T00:00:00Z
review text: The main theorem claims that a finite algebra \(\mathbf A\) admits Taylor operations if and only if it admits an idempotent 6-ary operation satisfying the identities: \(\omega (x,x,x,x,y,y)=\omega (x,y,x,y,x,x)\) and \(\omega (y,y,x,x,x,x)=\omega (x,x,y,x,y,x)\). This result implies that a locally finite variety omits the unary type if an only if it has an idempotent operation \(\omega\) satisfying the identities above. The author mentions that ``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''.
Mathematics Subject Classification ID: 08B05
Mathematics Subject Classification ID: 08A62
Mathematics Subject Classification ID: 08A70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5833769
zbMATH Keywords: Mal'tsev condition
zbMATH Keywords: omitting type 1
zbMATH Keywords: Taylor operation
author: Mark Siggers
reviewed by: Grigori I. Zhitomirski
MaRDI profile type: Publication
full work available at URL: s00012-010-0082-3
OpenAlex ID: W2035932556
cites work: The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
cites work: Varieties with few subalgebras of powers
cites work: \(H\)-coloring dichotomy revisited
cites work: Principles and Practice of Constraint Programming – CP 2003
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: On the complexity of H-coloring
cites work: The structure of finite algebras
cites work: On the algebraic structure of combinatorial problems
cites work: Q5471351
cites work: Existence theorems for weakly symmetric operations
cites work: A combinatorial constraint satisfaction problem dichotomy classification conjecture
cites work: Varieties Obeying Homotopy Laws
DOI: 10.1007/S00012-010-0082-3
Recommended article: Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
Recommended article: Optimal strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
Recommended article: On strong Mal'cev conditions for congruence meet-semidistributivity in a locally finite variety
Recommended article: A characterization of idempotent strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
Recommended article: Simpler Maltsev conditions for (weak) difference terms in locally finite varieties
Recommended article: Q4695973
Recommended article: Q4724692
Recommended article: A characterization of locally finite varieties that satisfy a nontrivial congruence identity
Recommended article: Mal'tsev conditions and representability of varieties
Recommended article: Q3775605
description: scientific article; zbMATH DE number 5833769