A finite relational structure A is called compact if for any infinite relational structure B of the same type, the existence of a homomorphism from B to A is equivalent to the existence of homomorphisms from all finite substructures of B to A. We show that if A has width one, then the compactness of A can be proved in the axiom system of Zermelo and Fraenkel, but otherwise, the compactness of A implies the existence of non-measurable sets in 3-space.

A graph $K$ is multiplicative if a homomorphism from any product $G \times H$ to $K$ implies a homomorphism from $G$ or from $H$. Hedetniemi's conjecture stated that all cliques are multiplicative. In an attempt to explore the boundaries of current methods, we investigate strongly multiplicative graphs, which we define as graphs $K$ such that for any connected graphs $G,H$ with odd cycles $C,C'$, a homomorphism from $(G \times C') \cup (C \times H) \subseteq G \times H$ to $K$ implies a homomorphism from $G$ or $H$. Strong multiplicativity of $K$ also implies the following property, which may be of independent interest: If $G$ is nonbipartite, $H$ is a connected graph with a vertex $h$, and there is a homomorphism $\phi\!: G \times H \rightarrow K$ such that $ \phi(-,h)$ is constant, then $H$ admits a homomorphism to $K$. All graphs currently known to be multiplicative are strongly multiplicative. We revisit the proofs in a different view based on covering graphs and replace fragments with more combinatorial arguments. This allows us to find new (strongly) multiplicative graphs: all graphs in which every edge is in at most one square, and the third power of any graph of girth $>$ 12. Though more graphs are amenable to our methods, they still make no progress for the case of cliques. Instead we hope to understand their limits, perhaps hinting at ways to further extend them.

We describe a generating set for the variety of simple graphs that admit a $k$-ary near-unanimity (NU) polymorphism. The result follows from an analysis of NU polymorphisms of strongly bipartite digraphs, i.e., whose vertices are either a source or a sink. We show that the retraction problem for a strongly bipartite digraph ${\mathbb H}$ has finite duality if and only if ${\mathbb H}$ admits an NU polymorphism. This result allows the use of tree duals to generate the variety of digraphs admitting a $k$-NU polymorphism.

We characterize obstruction sets in caterpillar dualities in terms of regular languages and give a construction of the dual of a regular family of caterpillars. In particular, we prove that every monadic linear Datalog program with at most one extensional database per rule defines the complement of a contraint satisfaction problem.

We describe a generating set for the variety of reflexive graphs that admit a compatible $k$-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of $j$-absolute retracts; in particular we show that the class of reflexive graphs with a 4-NU operation coincides with the class of 3-absolute retracts. Our results generalize and encompass several results on NU-graphs and absolute retracts.

We introduce a combinatorial parameter on finite relational trees which measures the smallest possible arity of a near-unanimity polymorphism on a core structure with finite duality.

We describe simple algebraic and combinatorial characterisations of finite relational core structures admitting finitely many obstructions. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores. A slight modification of this algorithm provides, for first-order definable CSP's, a simple poly-time algorithm to produce a solution when one exists. As an application of our algebraic characterisation of first order CSP's, we describe a large family of L-complete CSP's.

We characterise finite relational core structures admitting finitely many obstructions, in terms of special nearunanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores.

We prove that there exists a constant k such that for every $n \geq 1$ there exists a directed core graph $H_n$ with at least $2^n$ vertices such that a directed graph G is $H_n$-colorable if and only if every subgraph of G with at most $kn\log(n)$ vertices is $H_n$-colorable. Our examples show that in general the "duals of relational structures" in the sense of [J. Nesetril and C. Tardif, J. Combin. Theory Ser. B, 80 (2000), pp. 80-97] can have superpolynomial size. The construction given in this paper gives a double exponential upper bound for such a construction. Here we improve this to an exponential upper bound.