News and events
Gregory L. CherlinMODEL THEORY AND FINITE GROUPS [presentation]
I will describe some of the ways that the classification of the finite simple groups, or the methods used in that classification, have been applied in model theory, sometimes yielding information about the classification of finite structures. This leads to open questions about the computation or estimation of a certain invariant for finite permutation groups, which should be amenable to systematic treatment.
Robert Barham The Countably Categorical Trees and Partial Orders [blackboard presentation]
I shall give a classification of the countable categorical trees and partial orders by viewing countable categoricity as almost-transitivity.
The Gurarij space is the unique separable, universal and approximately homogeneous Banach space, analogous in many respects to the Urysohn space. In particular, one can construct the Gurarij space in a manner analogous to a construction for the Urysohn space due to Katetov. Using ideas of Uspenskij (for the Urysohn space), this can be used to show that the linear isometry group of the Gurarij space is a universal Polish group.
Several fundamental computational problems in phylogenetic reconstruction can be formulated as constraint satisfaction problems (CSPs) for structures that are first-order definable over the the homogeneous universal binary branching C-relation, denoted by C in the following. Examples of such problems is the rooted triple consistency problem, the quartet consistency problem, and the forbidden triples problem. We present a complete complexity classification for CSP(Γ) when Γ is first- order definable over C: such CSPs are either in P or NP-complete. The boarder between tractable and hard CSPs has an elegant universal-algeraic characterization: under the tech- nical assumption that Aut(Γ) is dense in End(Γ), we can show that EITHER Γ interprets all finite structures primitive positively (in which case CSP(Γ) is NP-hard), or there is a homomorphism f from Γ2 to Γ and an automorphism alpha of Γ satisfying f(x, y) = α(f(y, x)) (in which case CSP(Γ) is in P). This confirms a more general conjecture that applies to all omega-categorical structures for the special case of structures that are definable over C.
(joint work with Sam Tarzi and Claude Laflamme, Maurice Pouzet and Robert Woodrow)
The random graph is an endlessly fascinating object. In particular, its automorphism group has been much investigated, and there is still more to learn. Simon Thomas worked out all the reducts (equivalently, the closed overgroups of the automorphism group: these are automorphism groups of relational structures). But there are several methods of producing other kinds of overgroups, for example:
- weaken the condition of being an automorphism;
- allow structures derived from the random graph which are not relational (such as filters, topologies, or hypergraphs with infinite edge size).
Jan Foniok Ramsey Classes Defined by Forbidden Homomorphisms [overhead projector presentation]
I will talk about Ramsey properties of classes of digraphs (or more generally, relational structures) defined by forbidding homomorphisms from a fixed set of digraphs. Cases with infinitely many forbidden structures are of particular interest, especially if the forbidden "obstructions" are all trees or have bounded treewidth. These classes have several inter- esting applications, in areas such as complexity theory of constraint satisfaction problems.
We look at infinite graphs whose automorphisms have a certain degree of symmetry. In particular, we compare several transitivity conditions on infinite graphs (not necessarily countable), especially on those that have more than one end. We will see that these graphs have a treelike structure and that even relatively weak transitivity conditions lead to complete classifications of these graphs. The transitivity conditions we take care of are weakenings of homogeneity: The automorphisms act either distance-transitively (that is transitively on pairs of vertices of the same distance) or k-CS-transitively on the graphs (that is transitively on connected isomorphic subgraphs on $k$ vertices). For both situations, we present a complete list of infinite connected such graphs with more than one end.
Jan Hubicka Locally injective homomorphisms are universal 
It is well known that the homomorphism order on finite graphs is universal. This means that every countable partial order can be found as a suborder of the homomorphism order. The homomorphism order remain universal on number of restricted classes of graphs including the class of oriented paths. By the use of the arrow construction this result can be used to show universality of the homomorphism order on many classes of graphs and relational structures. A graph homomorphism is locally injective when its restriction to the neighborhood of every vertex is injective. We consider the partial order induced by the existence of locally injective homomorphisms. For this mapping it is not possible to apply the aforementioned result. We show that this partial order is universal on the class of connected graphs by new argument. We also overview the structure of this partial order in the context of degree decomposition matrices.
We extend the concept of nice topologies of H. Becker to the general case of Polish G-spaces (Becker assumed that G < Sym(ω)). Our apprach is based on continuous first order logic. Let (Y,d) be a Polish space and Iso(Y) be the corresponding isometry group endowed with the pointwise convergence topology. Then Iso(Y) is a Polish group. It is worth noting that any Polish group G can be realised as a closed subgroup of the isometry group Iso(Y) of an appropriate Polish space (Y,d). Moreover it is shown by J. Melleray that G can be chosen as the automorphism group of a continuous metric structure on Y$ which is approximately ultrahomogeneous. For any countable continuous signature L the set Y_L of all continuous metric L-structures on (Y,d) can be considered as a Polish Iso(Y)-space. We call this action logic and show that it is universal for Borel reducibility of orbit equivalence relations of Polish G-spaces with closed G <= Iso(Y). We investigate Polish G-spaces X for such G. Note that for any tuple s \in Y the map g → d(s,g(s)) can be considered as a graded subgroup of G. We consider G together with an appropriate family of such subgroups. Distinguishing some family B of graded subsets of X we arrive at the situation very similar to the logic space Y_L. For example treating elements of B as continuous formulas we obtain topological generalisations of several theorems from logic, for example Ryll-Nardzewski theorem.
Eric Jaligot Rigid embeddings [blackboard presentation]
Given a substructure X of a countable homogeneous structure M, is it possible to find specific embeddings of X into M in such a way that any automorphism of X extends to a unique automorphism of M? I will survey results on this natural question in various cases. If time permits, I will also consider the more general question of the universality of the automorphism group of M for the class of automorphism groups of its substructures, and the case where M is not homogeneous but still universal.
Eva Jungabel On homomorphism-homogeneous point-line geometries
In this talk we discuss one class of homomorphism-homogenous point-line geometries. A stucture S is homomorphism-homogeneous if every homomorphism from S' to S'', where S' and S'' are two finitely induced substructures, can be extended to an endomorphism of S. A point-line geometry is a non-empty finite set of points, together with a collectoin of subsets called lines such that every line contains at least two points and any pair of points is contained in at most one line. A line which contains more than two points is referred to as a regular line. A line wich contains exactly two points is called singular. Homomorphism-homogenous point-line geometries containing two regular intersecting lines have already been described. In order to complete the characterization of homomorphism-homogeneous point-line geometries it is necessary to describe homomorphism-homogenous point-line geometries where no two regular lines intersect. In this talk we first show that the problem of deciding homomorphism-homogeneity of a point-line geometry where no two regular lines intersect and there exist points that do not lie on regular lines is a coNP-complete problem. Therefore, we focus on point-line geometries where every point lies on a regular line. We fully classify point-line geometries with only two regular nonitersecting lines, and in the case of more than two regular pairwise nonintersecting lines we provide a partial classification.
We characterize retracts of Fraisse limits in terms of injectivity, improving a recent result of Dolinka. In particular, we characterize homomorphism-homogeneous structures as retracts of category-theoretic Fraisse limits. Among applications, we give a simple characterization of non-expansive retracts of the Urysohn space.
(joint work with Peter Cameron, Maurice Pouzet, Sam Tarzi, Robert Woodrow)
We are interested in overgroups of the automorphism group of the Rado graph. One class of such overgroups is completely understood; this is the class of reducts. In this article we tie recent work on various other natural overgroups, in particular establishing group connections between them and the reducts.
Cherlin posed the problem of classifying all the countable homogeneous n-graphs. Here, for n a positive integer, an n-graph is a structure whose domain is partitioned into n parts, each of which has a graph structure, and such that between each pair of parts there are finitely many possible edge types (which we think of as colours). I will present classification results (joint work with John Truss) in the special case of coloured multipartite graphs (that is, where each of the parts is a null graph). Using Fraisse's Theorem, the problem amounts to classifying the families F of finite coloured multipartite graphs for which the class Forb(F) of multipartite graphs which omit these is an amalgamation class. We are now able to give a complete characterisation of such families, for coloured multipartite graphs with any finite number of parts.
A structure is homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. The theory of (countable) homogeneous structures gained its momentum in 1953 with the famous theorem of Fraisse which states that countable homogeneous structures can be recognized by the fact that their collections of finitely induced substructures have the amalgamation property. Nowdays it is a well-established theory with deep consequences in many areas of mathematics. In their 2006 paper, P. Cameron and J. Nesetril discuss a variant of homogeneity with respect to various types of morphisms of structures, and in particular introduce the notion of homomorphism-homogeneous structures: a structure is called homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this talk we shall present an overview of classification results for some classes of finite structures including posets, graphs and point-line geometries. We shall also present an overview of a few known results on homomorphism-homogeneous algebras, and reflect on the problem of classifying homomorphism-homogeneous metric spaces.
Given a countable group Γ and a Polish group G, the space of all homomorphisms from Γ to G is naturally endowed with a Polish topological structure. When G is the automorphism group of some structure M, one may think of this space as being the space of all actions of Γ on M - and it becomes interesting to understand which properties are generic in the space of actions. When varying Γ and M, one obtains settings of a rather different flavour. I'll try to survey some of what is known, focusing on particular instances where M is either a homogeneous first-order structure of a homogeneous metric structure.
When constructing his universal countable graph, Richard Rado used the notion of universal functions. In this talk we will follow up on this idea by introducing the notion of universal homomorphisms and of universal homogeneous homomorphisms. The talk splits into five sections: 1) We will give sufficient conditions for their existence, 2.) we will use universal homomorphism to prove the existence of universal objects in classes of structured defined by hom-constraints, 3.) Using universal polymorphisms, we show that the Menger algebras of polymorphisms of several well-known homogeneous structures have uncountable cofinality and the Bergman property, 4.) we will characterize universal homogeneous retractions of homogeneous structures, 5.) will characterize all those homogeneous structures with the property that all retracts are induced by universal homogeneous retractions.
A countable relational structure is called weakly oligomorphic if its endomorphism monoid is oligomorphic (i.e. it has finitely many invariant relations of every arity). We show that every weakly oligomorphic relational structure is homomorphism-equivalent to a finite or ω-categorical core.
(joint work with Manuel Bodirsky)
An algebra with coutably infinite domain is called oligomorphic iff the set of its term functions contains an oligomorphic permutation group. We show that a classical theorem about finite algebras due to Birkhoff, called the finite HSP theorem, can be generalized to oligomorphic algebras. Birkhoff's HSP theorem states that a finite algebra B satisfies all equations that hold in a finite algebra A of the same signature if and only if B is a homomorphic image of a subalgebra of a finite power of A. We prove that if A and B are oligomorphic, then the mapping which sends each function from A to the corresponding function in B preserves equations *and is continuous* if and only if B is a homomorphic image of a subalgebra of a finite power of A. Our result has the following model-theoretic corollary: a theorem due to Ahlbrandt and Ziegler states that two omega-categorical countable structures are bi-interpretable if and only if their automorphsm groups are isomorphic as topological groups. It follows from our result that two such structures are *primitive positive* bi-interpretable if and only if their polymorphism clones are isomorphic as topological clones. In complexity theory, our result implies that the complexity of the constraint satisfaction problem of an omega-categorical structure only depends on its topological polymorphism clone.
(joint work with Yonatan Gutman and with Todor Tsankov)
Given a Fraisse class, it is natural to ask when it admits a "reasonable" expansion in a richer language which also has the Ramsey property. The purpose of this lecture is to present an answer to this question in terms of topological dynamics when "reasonable" means that every element of the original class only has finitely many expansions in the richer language.
If G is a topological group, a G-flow is a compact space equipped with a continuous action of G. Of special interest are the minimal flows (those that do not admit proper subflows) because of their rich structure and the fact that any flow must contain a minimal subflow. In the case where G is locally compact, non-compact, there is a great variety of minimal flows and a classification seems to be infeasible. On the other hand, for many naturally occurring non-locally compact groups, there is only one minimal flow -- a single point -- and the situation trivializes. In this talk, I will concentrate on an intermediate example, that of the group of all permutations of the integers, S_infty. It turns out that S_infty has only countably many minimal flows that can be described quite explicitly (they are all given by the logic action of S_infty on the space of models of certain universal theories). This classification relies in an essential way on previous work of Glasner and Weiss, who had identified the universal minimal flow of S_infty, of which all other minimal flows are quotients.
Modified: 16. 5. 2012