A strong Mal'cev condition for locally finite varieties omitting the unary type
From MaRDI portal
Publication:616117
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.
Recommendations
- Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
- Optimal strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
- On optimal strong Mal'cev conditions for congruence meet-semidistributivity in a locally finite variety
- A characterization of idempotent strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
- Simpler Maltsev conditions for (weak) difference terms in locally finite varieties
- scientific article; zbMATH DE number 220084
- scientific article; zbMATH DE number 3997884
- A characterization of locally finite varieties that satisfy a nontrivial congruence identity
- Mal'tsev conditions and representability of varieties
- scientific article; zbMATH DE number 4035898
Cites work
- H-coloring dichotomy revisited
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- An algebraic approach to multi-sorted constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- Existence theorems for weakly symmetric operations
- scientific article; zbMATH DE number 5030273 (Why is no real title available?)
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The structure of finite algebras
- Varieties Obeying Homotopy Laws
- Varieties with few subalgebras of powers
Cited in
(45)- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- A complexity dichotomy for signed \(\mathbf{H}\)-colouring
- The wonderland of reflections
- Taylor term does not imply any nontrivial linear one-equality Maltsev condition
- A characterization of idempotent strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
- Galois connections for patterns: an algebra of labelled graphs
- Loop conditions
- Random models of idempotent linear Maltsev conditions. I. Idemprimality
- Characterizations of several Maltsev conditions.
- A quasi-Mal'cev condition with unexpected application.
- Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
- Dichotomy for finite tournaments of mixed-type
- The constraint satisfaction problem and universal algebra
- Optimal strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
- The weakest nontrivial idempotent equations
- A dichotomy for first-order reducts of unary structures
- The language of stratified sets is confluent and strongly normalising
- The structure of polynomial operations associated with smooth digraphs.
- A juggler's dozen of easy\(^\dag\) problems (\(^\dag\) Well, easily formulated \dots).
- Loop conditions for strongly connected digraphs
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Absorption in universal algebra and CSP
- The complexity of valued CSPs
- PROJECTIVE CLONE HOMOMORPHISMS
- A note on the weakest Taylor term
- When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
- Testing the Complexity of a Valued CSP Language
- Hybrid VCSPs with crisp and valued conservative templates
- \( \omega \)-categorical structures avoiding height 1 identities
- Solving equation systems in ω-categorical algebras
- Pseudo‐loop conditions
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- Learnability of solutions to conjunctive queries
- On solvability of systems of polynomial equations
- Deciding the existence of quasiweak near unanimity terms in finite algebras
- The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
- The smallest hard trees
- Universal algebraic methods for non-classical logics
- Varieties defined by basic equations have the amalgamation property
- Ivo G. Rosenberg's work on maximal clones and minimal clones
- Injective hardness condition for PCSPs
- Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
- A complexity dichotomy in spatial reasoning via Ramsey theory
- Three fundamental questions in modern infinite-domain constraint satisfaction
- In praise of homomorphisms
This page was built for publication: A strong Mal'cev condition for locally finite varieties omitting the unary type
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616117)
