Abstract It is known that a countable $\omega $ -categorical structure interprets all finite structures primitively positively if and only if its polymorphism clone maps to the clone of projections on a two-element set via a continuous clone homomorphism. We investigate the relationship between the existence of a clone homomorphism to the projection clone, and the existence of such a homomorphism which is continuous and thus meets the above criterion.

Let $C$ denote a binary linear code with length $n$ all of whose coordinates are essential; i.e., for each coordinate there is a codeword that is not zero in that position. Then the maximum distance $D$ is strictly bigger than $n/2$, and the extremum $D=(n+1)/2$ is attained exactly by punctured Hadamard codes. In this paper, we classify binary linear codes with $D=n/2+1$. All of these codes can be produced from punctured Hadamard codes in one of essentially three different ways, each having a transparent description.

For $n\geq 3$, let $(H_n, E)$ denote the $n$th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on $n$ vertices. We show that for all structures $\Gamma$ with domain $H_n$ whose relations are first-order definable in $(H_n,E)$ the constraint satisfaction problem for $\Gamma$ either is in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete.

A partial order is called semilinear if the upper bounds of each element are linearly ordered and any two elements have a common upper bound. There exists, up to isomorphism, a unique countable existentially closed semilinear order, which we denote by |$(\mathbb{S}_{2};\leq )$|⁠. We study the reducts of |$(\mathbb{S}_{2};\leq )$|⁠, that is, the relational structures with domain |$\mathbb{S}_{2}$|⁠, all of whose relations are first-order definable in |$(\mathbb{S}_{2};\leq )$|⁠. Our main result is a classification of the model-complete cores of the reducts of |$\mathbb{S}_{2}$|⁠. From this, we also obtain a classification of reducts up to first-order interdefinability, which is equivalent to a classification of all subgroups of the full symmetric group on |$\mathbb{S}_{2}$| that contain the automorphism group of |$(\mathbb{S}_{2};\leq )$| and are closed with respect to the pointwise convergence topology.