# Workshop on Universal Algebra, Complexity and CSP, June 2010

The research group in Universal Algebra at CAUL organizes a workshop on algebra and complexity questions on June 28-29, 2010. Talks will take place in room B2.01 at CAUL, Av. Prof. Gama Pinto 2, Lisbon, Portugal.

### Preliminary schedule

Monday, June 28

 10:00 - 11:00 Peter Mayr CAUL Subpower-Membership and Interpolation 11:30 - 12:30 Miklos Maroti University Szeged Tree over Maltsev 14:00 - 15:00 Michael Pinsker Universite Paris 7 Decidability of pp-Definability 15:30 - 16:30 Catarina Carvalho CAUL Maltsev Digraphs

Monday night's dinner is still TBD.
Tuesday, June 29

 10:00 - 11:00 Libor Barto Charles University, Prague An application of CSP to universal algebra: A proof of "The Crazy Zadori's Conjecture" 11:30 - 12:30 Petar Markovic University Novi Sad Combining semilattices and abelian algebras to solve CSP 14:00 - 15:00 Janusz Konieczny University of Mary Washington Automorphism Groups of Endomorphism Monoids of Reflexive Digraphs 15:00 - 16:00 All Discussion

### Abstracts

Title:  An application of CSP to universal algebra: A proof of "The Crazy Zadori's Conjecture"
Speaker:  Libor Barto

Abstract:
In last ten years universal algebra played a major role in the study of the complexity of constraint satisfaction problems.
On the other hand, tools developed for CSP and also "CSP viewpoint" brought new results and insights to universal algebra:
A big progress has been made in understanding various kinds of Mal'cev conditions and relations between them; a well known conjecture about number of Mal'cev clones has been confirmed (Aichinger, Mayr, McKenzie); .... I will discuss one example of such an application - we give an affirmative answer to the following conjecture: Every finite, finitely related algebra generating a congruence distributive variety has a near-unanimity term operation.

Title:  Maltsev Digraphs
Speaker:  Catarina Carvalho

Abstract:
We characterize digraphs preserved by Maltsev polymorphisms.

Title:  Automorphism Groups of Endomorphism Monoids of Reflexive Digraphs
Speaker:  Janus Konieczny

Abstract:
For a mathematical structure $\mathcal{A}$, let $\mbox{End}(\mathcal{A})$ denote the monoid of endomorphisms of $\mathcal{A}$. A significant amount of research has been devoted to the study of relations between the monoid $\mbox{End}(\mathcal{A})$ and the structure $\mathcal{A}$ itself. Along this line of research, the description of the automorphism group of $\mbox{End}(\mathcal{A})$ has been of particular interest. In 1936, J. Schreier proved that for an unstructured set $X$, the automorphism group of the monoid $\mbox{End}(X)$ is isomorphic to the symmetric group $\mbox{Sym}(X)$ on $X$. Since then, the automorphism groups of $\mbox{End}(\mathcal{A})$ have been obtained for various other structures $\mathcal{A}$ such as orders, equivalence relations, graphs, and hypergraphs. In this talk, the structure $\mathcal{A}$ will be an arbitrary reflexive directed graph (digraph), that is, $\mathcal{A}=(X,\rho)$, where $X$ is an arbitrary set and $\rho$ is a reflexive binary relation on~$X$. I will present recent results (1) that determine the automorphism group of the monoid $\mbox{End}(X,\rho)$ for several classes of reflexive digraphs $(X,\rho)$.
(1) These results have been obtained jointly with João Araújo (CAUL, Portugal) and Edward Dobson (Mississippi State University, USA).

Title:  Subpower-Membership and Interpolation
Speaker:  Peter Mayr

Abstract:
In a talk in Nashville three years ago Ross Willard defined the subpower membership problem for a fixed finite algebraic structure A as follows:
INPUT: a subset X of A^n and a tuple y in A^n
PROBLEM: Is y in the subalgebra of A^n that is generated by X?
From Marcin Kozik's work it follows that this decision problem is Exptime-complete in general. However, a polynomial time algorithm is known for groups -- possibly with additional, multilinear operations (e.g., groups, rings, modules, algebras over fields, ...).
I will discuss this algorithm and some recent results on certain Malcev algebras with subpower membership problem in P.

Title:  Decidability of pp-Definability
Speaker:  Michael Pinsker

Abstract:
For a fixed infinite structure with finite signature $\tau$, we study the following computational problem: given quantifier-free first-order formulas $\phi_ 0, \phi_ 1, \ldots , \phi_n$ that define relations $R_0, R_1, \ldots ,R_n$ over $\tau$, is the relation $R_0$ primitive positive definable in the structure $(D;R_1, \ldots ,R_n)$, i.e., definable by a first-order formula that uses only relation symbols for $R_1,\ldots ,R_n$, equality, conjunctions, and existential quantification (disjunction, negation, and universal quantification are forbidden). We show decidability of our problem for a large class of homogeneous structures $\Gamma$. The assumptions on $\Gamma$ are that the class $C$ of finite induced substructures of $\Gamma$ can be described by a finite set of finite forbidden substructures and that $C$ is a Ramsey class (examples for structures with these properties are the dense linear order, and ordered versions of the random graph, the homogeneous universal poset, the random tournament, the homogeneous universal C-relation, and many more). Our proof makes use of universal-algebraic concepts, Ramsey theory, and a characterization of Ramsey classes in topological dynamics.

Back to the CAUL-website.