The classification of homomorphism homogeneous tournaments

The notion of homomorphism homogeneity was introduced by Cameron and Nešetřil as a natural generalization of the classical model-theoretic notion of homogeneity. A relational structure is called homomorphism homogeneous (HH) if every homomorphism between finite substructures extends to an endomorphism. It is called polymorphism homogeneous (PH) if every finite power of the structure is homomorphism homogeneous. Despite the similarity of the definitions, the HH and PH structures lead a life quite separate from the homogeneous structures. While the classification theory of homogeneous structure is dominated by Fraïssé-theory, other methods are needed for classifying HH and PH structures. In this paper we give a complete classification of HH countable tournaments (with loops allowed). We use this result in order to derive a classification of countable PH tournaments. The method of classification is designed to be useful also for other classes of relational structures. Our results extend previous research on the classification of finite HH and PH tournaments by Ilić, Mašulović, Nenadov, and the first author.     

Countable infinite existentially closed models of universally axiomatizable theories

In the present article, we obtain a new criterion for amodel of a universally axiomatizable theory to be existentially closed. The notion of a maximal existential type is used in the proof and for investigating properties of countable infinite existentially closed structures. The notions of a prime and a homogeneous model, which are classical for the general model theory, are introduced for such structures. We study universal theories with the joint embedding property admitting a single countable infinite existentially closed model. We also construct, for every natural n, an example of a complete inductive theory with a countable infinite family of countable infinite models such that n of them are existentially closed and exactly two are homogeneous.     

On Vaught’s Conjecture and finitely valued MV algebras

We show that the complete first order theory of an MV algebra has $2^{\aleph _0}$ countable models unless the MV algebra is finitely valued. So, Vaught's Conjecture holds for all MV algebras except, possibly, for finitely valued ones. Additionally, we show that the complete theories of finitely valued MV algebras are $2^{\aleph _0}$ and that all ω‐categorical complete theories of MV algebras are finitely axiomatizable and decidable. As a final result we prove that the free algebra on countably many generators of any locally finite variety of MV algebras is ω‐categorical.     

On the Boolean algebras of definable sets in weakly o‐minimal theories

We consider the sets definable in the countable models of a weakly o‐minimal theory T of totally ordered structures. We investigate under which conditions their Boolean algebras are isomorphic (hence T is p‐ω‐categorical), in other words when each of these definable sets admits, if infinite, an infinite coinfinite definable subset. We show that this is true if and only if T has no infinite definable discrete (convex) subset. We examine the same problem among arbitrary theories of mere linear orders. Finally we prove that, within expansions of Boolean lattices, every weakly o‐minimal theory is p‐ω‐categorical. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Connected‐Homomorphism‐Homogeneous Graphs

A relational structure is (connected‐) homogeneous if every isomorphism between finite (connected) substructures extends to an automorphism of the structure. We investigate notions that generalise (connected‐) homogeneity, where ‘isomorphism’ may be replaced by ‘homomorphism’ or ‘monomorphism’ in the definition. In particular, we study the classes of finite connected‐homomorphism‐homogeneous graphs, with the aim of producing classifications. The main result is a classification of the finite graphs, where a graph G is if every homomorphism from a finite connected induced subgraph of G into G extends to an endomorphism of G. The finite (connected‐homogeneous) graphs were classified by Gardiner in 1976, and from this we obtain classifications of the finite and finite graphs. Although not all the classes of finite connected‐homomorphism‐homogeneous graphs are completely characterised, we may still obtain the final hierarchy picture for these classes.     

Two Fraïssé-style theorems for homomorphism–homogeneous relational structures

In this paper, we state and prove two Fraïssé-style results that cover existence and uniqueness properties for twelve of the eighteen different notions of homomorphism–homogeneity as introduced by Lockett and Truss, and provide forward directions and implications for the remaining six cases. Following these results, we completely determine the extent to which the countable homogeneous undirected graphs (as classified by Lachlan and Woodrow) are homomorphism–homogeneous; we also provide some insight into the directed graph case.     

ω‐categorical weakly o‐minimal expansions of Boolean lattices

We study ω‐categorical weakly o‐minimal expansions of Boolean lattices. We show that a structure ?? = (A,≤, ?) expanding a Boolean lattice (A,≤) by a finite sequence I of ideals of A closed under the usual Heyting algebra operations is weakly o‐minimal if and only if it is ω‐categorical, and hence if and only if A/I has only finitely many atoms for every I ∈ ?. We propose other related examples of weakly o‐minimal ω‐categorical models in this framework, and we examine the internal structure of these models.     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.     

Binary types in ℵ0‐categorical weakly o‐minimal theories

Orthogonality of all families of pairwise weakly orthogonal 1‐types for ?₀‐categorical weakly o‐minimal theories of finite convexity rank has been proved in 6 . Here we prove orthogonality of all such families for binary 1‐types in an arbitrary ?₀‐categorical weakly o‐minimal theory and give an extended criterion for binarity of ?₀‐categorical weakly o‐minimal theories (additionally in terms of binarity of 1‐types). © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Homomorphism–homogeneous graphs

We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–homogeneity. Further, we show that there are homomorphism–homogeneous graphs that do not contain the Rado graph as a spanning subgraph answering the second open question. We also treat the case of homomorphism–homogeneous graphs with loops allowed, showing that the corresponding decision problem is co–NP complete. Finally, we extend the list of considered morphism–types and show that the graphs for which monomorphisms can be extended to epimor‐phisms are complements of homomorphism–homogeneous graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 253–261, 2010     

Unitary Representations of Oligomorphic Groups

We obtain a complete classification of the continuous unitary representations of oligomorphic permutation groups (those include the infinite permutation group S ^??, the automorphism group of the countable dense linear order, the homeomorphism group of the Cantor space, etc.). Our main result is that all irreducible representations of such groups are obtained by induction from representations of finite quotients of open subgroups and, moreover, every representation is a sum of irreducibles. As an application, we prove that many oligomorphic groups have property (T). We also show that the Gelfand?CRaikov theorem holds for topological subgroups of S ^??: for all such groups, continuous irreducible representations separate points in the group.     

Filling certain cuts in discrete weakly o‐minimal structures

Discrete weakly o‐minimal structures, although not so stimulating as their dense counterparts, do exhibit a certain wealth of examples and pathologies. For instance they lack prime models and monotonicity for definable functions, and are not preserved by elementary equivalence. First we exhibit these features. Then we consider a countable theory of weakly o‐minimal structures with infinite definable discrete (convex) subsets and we study the Boolean algebra of definable sets of its countable models. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Random graphons and a weak Positivstellensatz for graphs

In an earlier article, the authors proved that limits of convergent graph sequences can be described by various structures, including certain 2‐variable real functions called graphons, random graph models satisfying certain consistency conditions, and normalized, multiplicative and reflection positive graph parameters. In this article we show that each of these structures has a related, relaxed version, which are also equivalent. Using this, we describe a further structure equivalent to graph limits, namely probability measures on countable graphs that are ergodic with respect to the group of permutations of the nodes. As an application, we prove an analogue of the Positivstellensatz for graphs: we show that every linear inequality between subgraph densities that holds asymptotically for all graphs has a formal proof in the following sense: it can be approximated arbitrarily well by another valid inequality that is a “sum of squares” in the algebra of partially labeled graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory     

On diverse forms of homogeneity of Lie algebras

In the paper, several different ways to introduce the notion of homogeneity in the case of finite-dimensional Lie algebras are considered. Among these notions, we have homogeneity, almost homogeneity, weak homogeneity, and projective homogeneity. Constructions and examples of Lie algebras of diverse forms of homogeneity are presented. It is shown that the notions of weak homogeneity and of weak projective homogeneity are the most nontrivial and interesting for a detailed investigation. Some structural properties are proved for weakly homogeneous and weakly projectively homogeneous Lie algebras.     

Preservation of <Emphasis Type="Italic">ω</Emphasis>-Categoricity In Expanding The Models of Weakly <Emphasis Type="Italic">o</Emphasis>-Minimal Theories

Studying the model-theoretic properties that are preserved under expansion of the models of countably categorical weakly o-minimal theories of finite convexity rank with convex unary predicates, we show that countable categoricity and convexity rank are among these properties.     

Equational partiality

A special kind of partiality of heterogeneous algebraic structures is introduced. Every operator of a heterogeneous operator domain is associated with a set of term equations as necessary and sufficient domain condition.It is shown that some kind of hierarchy condition for the system of domain equations is equivalent to the condition that every injective weak homomorphism is a strong homomorphism which is equivalent to the statement that every bijective weak homomorphism is an isomorphism.On the base of this result the notions of a quasi-variety and of a variety of equationally partial heterogeneous algebras are suggested. The class of all small categories becomes a standard example of a variety of equational partial heterogeneous algebras.Presented by V. Trnková.     

Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs

In this article, we introduce and study the properties of some target graphs for 2‐edge‐colored homomorphism. Using these properties, we obtain in particular that the 2‐edge‐colored chromatic number of the class of triangle‐free planar graphs is at most 50. We also show that it is at least 12.     

Dimensions, matroids, and dense pairs of first-order structures

A structure M is pregeometric if the algebraic closure is a pregeometry in all structures elementarily equivalent to M. We define a generalisation: structures with an existential matroid. The main examples are superstable groups of Lascar U-rank a power of ω and d-minimal expansion of fields. Ultraproducts of pregeometric structures expanding an integral domain, while not pregeometric in general, do have a unique existential matroid.Generalising previous results by van den Dries, we define dense elementary pairs of structures expanding an integral domain and with an existential matroid, and we show that the corresponding theories have natural completions, whose models also have a unique existential matroid. We also extend the above result to dense tuples of structures.     

A uniform Birkhoff theorem

Birkhoff’s HSP theorem characterizes the classes of models of algebraic theories as those being closed with respect to homomorphic images, subalgebras, and products. In particular, it implies that an algebra B satisfies all equations that hold in an algebra A of the same signature if and only if B is a homomorphic image of a subalgebra of a (possibly infinite) direct power of A. The former statement is equivalent to the existence of a natural map sending term functions of the algebra A to those of B—the natural clone homomorphism. The study of continuity properties of natural clone homomorphisms has been initiated recently by Bodirsky and Pinsker for locally oligomorphic algebras.Revisiting the argument of Bodirsky and Pinsker, we show that for any algebra B in the variety generated by an algebra A, the induced natural clone homomorphism is uniformly continuous if and only if every finitely generated subalgebra of B is a homomorphic image of a subalgebra of a finite power of A. Based on this observation, we study the question as to when Cauchy continuity of natural clone homomorphisms implies uniform continuity. We introduce the class of almost locally finite algebras, which encompasses all locally oligomorphic as well as all locally finite algebras, and show that, in case A is almost locally finite, then the considered natural homomorphism is uniformly continuous if (and only if) it is Cauchy-continuous. In particular, this provides a locally finite counterpart of the result by Bodirsky and Pinsker. Along the way, we also discuss some peculiarities of oligomorphic permutation groups on uncountable sets.     

On diagonal actions of branch groups and the corresponding characters

We introduce notions of absolutely non-free and perfectly non-free group actions and use them to study the associated unitary representations. We show that every weakly branch group acting on a regular rooted tree acts absolutely non-freely on the boundary of the tree. Using this result and the symmetrized diagonal actions we construct for every countable branch group infinitely many different ergodic perfectly non-free actions, infinitely many II₁-factor representations, and infinitely many continuous ergodic invariant random subgroups.