Identities in finite Taylor algebras

Abstract

Eine endliche, idempotente Algebra heißt Taylor, wenn sie ein System nichttrivialer Gleichungen erfüllt. Dabei wird eine Algebra idempotent genannt, wenn für jede ihrer Termoperationen f die Identität f (x, . . . , x) = x gilt. Ein tiefliegendes Ergebnis von M. Maróti und R. McKenzie besagt, dass eine endliche, idempotente Algebra genau dann Taylor ist, wenn sie eine weak near-unanimity- (WNU-) Termoperation besitzt, also eine Termoperation w, die die Identitäten w(x, . . . , x, y) = w(x, . . . , y, x) = · · · = w(y, x, . . . , x) erfüllt. WNU-Termoperationen spielten eine Schlüsselrolle beim Nachweis der lange ungelösten Dichotomie-Vermutung für Constraint Satisfaction Problems (CSPs) über einer endlichen Menge Γ von Relationen auf einer endlichen Domäne: CSP(Γ) ist genau dann in polynomieller Zeit lösbar, wenn Γ von einer WNU-Termoperation erhalten wird. Die Theorie der loop conditions fußt auf der Beobachtung, dass die Erfüllung von Identitäten der Form f (x1,1, . . . , x1,n) = f (x2,1, . . . , x2,n) = · · · = f (xk,1, . . . , xk,n) durch eineTermoperation f einer Algebra äquivalent zur Existenz eines konstanten Tupels in einer zugehörigen Relation ist. Die durch eine WNU-Termoperation induzierte Relation erweist sich als symmetrisch. Die Charakterisierung von endlichen, idempotenten Taylor-Algebren durch die Existenz von WNU-Termoperationen ergibt sich nun durch die Tatsache, dass jede nichtleere, symmetrische und invariante Relation einer geeigneten Arität, die auf einer endlichen, idempotenten Taylor-Algebra definiert ist, ein konstantes Tupel enthält. Von diesem Punkt aus beginnen wir mit der systematischen Untersuchung von k-WNU-Termoperationen, einer Verallgemeinerung von WNU-Termoperationen. Die Relation, die durch die eine k-WNU-Termoperation der Arität n definierende loop condition hervorgeht, besitzt die Invarianzeigenschaft der (n, k)-Symmetrie. Das Hauptziel dieser Arbeit ist, hinreichende Bedingungen an n zu finden, die die Existenz eines konstanten Tupels in jeder nichtleeren, (n, k)-symmetrischen und invarianten Relation auf einer endlichen, idempotenten Taylor-Algebra garantieren und somit die Existenz einer k-WNU-Termoperation der Arität n implizieren.

A finite idempotent algebra is said to be Taylor if it satisfies a set of nontrivial identities. Here, an algebra is called idempotent if the identity f (x, . . . , x) = x holds for any of its term operations f . By a deep theorem of M. Maróti and R. McKenzie, a finite idempotent algebra is Taylor if and only if it possesses a weak near-unanimity (WNU) term operation, i.e., an operation w satisfying the identities w(x, . . . , x, y) = w(x, . . . , y, x) = · · · = w(y, x, . . . , x). WNU term operations played a key role in proving the long-unsolved dichotomy conjecture for finite-domain Constraint Satisfaction Problems (CSPs): CSP(Γ) is tractable if and only if Γ is preserved by a WNU term operation. The theory of loop conditions is based on the observation that the satisfaction of identities of the form f (x1,1, . . . , x1,n) = f (x2,1, . . . , x2,n) = · · · = f (xk,1, . . . , xk,n) by a term operation f of an algebra is equivalent to the existence of a constant tuple in an associated relation. The relation associated with a WNU term operation turns out to be symmetric. The characterisation of finite idempotent Taylor algebras by the existence of WNU term operations now arises from the fact that any nonempty, symmetric, and invariant relation of an appropriate arity defined on a finite idempotent Taylor algebra contains a constant tuple. From this point of origin we initiate the systematic study of k-WNU term operations, which generalise the notion of WNU term operations. The relation associated with the loop condition defining a k-WNU term operation of arity n has the invariance property of being (n, k)-symmetric. The main goal of this thesis is to find sufficient conditions on n that guarantee the existence of a constant tuple in any nonempty, (n, k)-symmetric, and invariant relation on a finite idempotent Taylor algebra, and thus imply the existence of a k-WNU term operation of arity n.