# Schedule of the Workshop on Homogeneous Structures

## Monday, October 28

 10:00 - 11:00 S.Solecki: Dual Ramsey theorem for trees 11:00 - 11:30 Coffee break 11:30 - 12:30 M.Bodirsky: Countably categorical structures and the computational complexity of constraint satisfaction problems 12:30 - 13:45 Lunch break 13:45 - 14:45 M.Pinsker: Reconstructing the topology of clones 15:00 - 16:00 D.Evans: Countable structures with simple automorphism groups 16:00 - 16:30 Tea and cake 16:30 - 17:30 A.Vershik: The nonstandardness in the deterministic and random dynamics, and in combinatorics

## Tuesday, October 29

 10:00 - 11:00 G.Cherlin: Universal graphs with forbidden subgraphs 11:00 - 11:30 Coffee break 11:30 - 12:30 I.Ben Yaacov: Stability, WAP, and Roelcke-precompact Polish groups 12:30 - 13:45 Lunch break 13:45 - 14:15 A.Pongrácz: The 42 reducts of the random ordered graph 14:15 - 14:45 P.Wesolek: Conjugacy classes in locally compact subgroups of S∞ 15:00 - 16:00 C.Laflamme: Ramsey precompact expansions of homogeneous directed graphs 16:00 - 16:30 Tea and cake

## Wednesday, October 30

 10:00 - 11:00 M.Droste: Random constructions imply symmetry 11:00 - 11:30 Coffee break 11:30 - 12:30 E.Glasner: On tame dynamical systems 12:30 - 14:00 Lunch break 14:00 - 14:30 D.Bartošová: The universal minimal flow of the group of automorphisms of P(ω1)/fin 15:00 - 16:00 D.Macpherson: Set-­‐homogeneous structures and orbit-­‐equivalent permutation groups 16:00 - 16:30 Tea and cake 16:30 - 17:30 S.Todorcevic: Forcing associated with homogeneous indivisible structures 18:00 - Reception

## Thursday, October 31

 10:00 - 11:00 J.Nesetril: Towards Characterization of Ramsey classes 11:00 - 11:30 Coffee break 11:30 - 12:30 J.Melleray: Metric homogeneous structures 12:30 - 13:45 Lunch break 13:45 - 14:15 M.Sokic: Semilattices 14:15 - 14:45 O.Kwiatkowska: Lelek fan from a projective Fraïssé limit 15:00 - 16:00 T.Tsankov: On some generalizations of de Finetti’s theorem 16:00 - 16:30 Tea and cake

# Abstracts

(Underlined titles can be clicked for the video recording)

#### D. Bartošová: The universal minimal flow of the group of automorphisms of P(ω1)/fin

 Abstract.pdf The_Presentation_Slides.pdf
Top

#### I. Ben Yaacov: Stability, WAP, and Roelcke-precompact Polish groups

In joint work with T. Tsankov we study a (yet other) point at which model theory and dynamics intersect.
On the one hand, a (metric) aleph_0-categorical structure is determined, up to bi-interpretability, by its automorphism group, while on the other hand, such automorphism groups are exactly the Roelcke precompact ones. One can further identify formulae on the one hand with Roelcke-continuous functions on the other hand, and similarly stable formulae with WAP functions, providing an easy tool for proving that a group is Roelcke precompact and for calculating its Roelcke/WAP compactification.
Model-theoretic techniques, transposed in this manner into the topological realm, allow one to prove further that if  R(G) = W(G)  then G  is totally minimal.

Top

#### M. Bodirsky: Countably Categorical Structures and the Computational Complexity of Constraint Satisfaction Problems

Many computational problems in theoretical computer science can be modeled as  constraint satisfaction problems (CSPs) for countably categorical structures. One of the most fundamental questions is to determine which CSPs can be solved in polynomial time, and which are NP-hard. In recent years, concepts and results from universal algebra and Ramsey theory have lead to several strong complexity classification results. This approach has also led to research questions that should be of independent interest in model theory, topological dynamics, and combinatorics -- also see the talks of Pinsker and Pongrácz. In this talk, I will give an introduction to CSPs, complexity classification, and the mentioned links with the topics of the workshop.

 bodirsky.pdf
Top

#### G. Cherlin: Universal graphs with forbidden subgraphs

 Universal_graphs_with_forbidden_subgraphs.pdf The_presentation_slides.pdf
Top

#### M. Droste: Random constructions imply symmetry

We will argue for the claim of the title in the areas of algebra, theoretical computer science, and theoretical physics. In algebra, we will consider the fundamental theorem of Ulm for countable abelian p-groups. For theoretical computer science, we will give a probabilistic construction of Scott domains and show that with probability 1 our construction produces a universal homogeneous domain. Finally, we consider causal sets which have been used as basic models for discrete space-time in quantum gravity.

Top

#### D. Evans: Countable structures with simple automorphism groups

We report on some joint work with Zaniar Ghadernezhad and Katrin Tent. A result of Daniel Lascar from 1992 shows that the automorphism groups of countable almost strongly minimal structures are simple modulo a normal subgroup of bounded' automorphisms. This includes the classical results that  the symmetric group of countable degree modulo the finitary permutations is simple, and the general linear group of a countable dimensional vector space over a countable field is simple modulo the finitary linear transformations. Recent work of Macpherson and Tent used ideas from Lascar's paper to show the simplicity of the automorphism groups of a large class of homogeneous structures obtained from free amalgamation classes. This was generalised in work of Tent and Ziegler to study the simplicity of the automorphism groups of countable structures which support a stationary independence relation.' We extend this work to a wider context and use it to show that various countable structures obtained using the Hrushovski amalgamation method (and an integer-valued predimension) have simpleautomorphism groups. These include the structures of infinite Morley rank obtained using the most basic form of the construction and the omegacategorical examples.

 evans.pdf

#### E. Glasner: On tame dynamical systems

 On_tame_dynamical_systems.pdf
Top

#### O. Kwiatkowska: Lelek fan from a projective Fraïssé limit

The Lelek fan is the unique up to homeomorphism compact and connected subspace of the cone over the Cantor set that has a dense set of endpoints. We show how to obtain the Lelek fan as a quotient of a projective Fraïssé limit. Then we discuss some properties and questions concerning the homeomorphism group of the Lelek fan. This is joint work with Dana Bartošová.

 kwiatkowska.pdf
Top

#### C. Laflamme: Ramsey precompact expansions of homogeneous directed graphs

In their 2005 paper, Kechris, Pestov and Todorcevic provided a powerful tool to compute an invariant of topological groups known as the universal minimal flow, immediately leading to an explicit representation of this invariant in many concrete cases. More recently, Nguyen Van The generalized the framework which could now be applied to several new cases. We will review these new methods, and apply them in the context of all homogeneous directed graphs. Moreover, we verify the relative expansion properties and consequently describe the respective universal minimal flows. We will conclude with some open problems and conjectures.

 laflamme.pdf
Top

#### D. Macpherson: Set-homogeneous structures and orbit-equivalent permutation groups

We call a countable relational structure M ‘set-homogeneous', if, whenever two finite substructures U,V are isomorphic, there is an automorphism of M taking U to V (but we do not require that every isomorphism extends). I will discuss recent work with Gray, Praeger and Royle on this notion, and much earlier work with Droste, Giraudet, and Sauer. There is a classification of finite set-homogeneous digraphs, and initial results on countably-infinite set-homogeneous graphs and digraphs. The question leads naturally to a related notion which has been extensively examined for finite permutation groups. Two permutation groups G,H on a set X are called `orbit-equivalent' if, for all finite k, they have the same orbits on the collection of unordered k-element subsets of X. I will describe recent work with Lockett, showing that if G,H are topologically closed orbit-equivalent permutation groups on an infinite set X, with H a subgroup of G, and G is primitive but not 2-transitive, then G=H.

Top

#### J. Melleray: Metric homogeneous structures

The class of automorphism groups of Polish metric structures is the same as the class of all Polish groups; this simple observation leads one to try and extend the well-known interplay between model theory and descriptive set theory of closed permutation groups to the context of metric model theory and Polish groups. A key point when studying automorphism groups of non-discrete structures is the appearance of a natural uniform metric, leading to the notion of topometric group structure. Intuitively, the notion of "point" is replaced by that of a "point up to a small, uniform error"; in essence, one is replacing points with functions. I will present the beginnings of an analogue of descriptive set theory in that context, and a topometric analogue of a classical theorem of Effros. This is joint work with Itaï Ben Yaacov (Lyon).

 melleray.pdf
Top

#### J. Nesetril: Towards Characterization of Ramsey classes

We survey the recent results on this program and present some new Ramsey classes.They in turn relates to some universal graphs studied earlier.

Top

#### M. Pinsker: Reconstructing the topology of clones

Any countable omega-categorical structure $\Delta$ can be reconstructed up to first-order interdefinability from its automorphism group, by the theorem of Ryll-Nardzewski. Even more information about $\Delta$ is encoded into its polymorphism clone, i.e., the set of all finitary functions on its domain which preserve $\Delta$: the polymorphism clone still "knows'' $\Delta$ up to primitive positive interdefinability (Bodirsky+Nesetril). If we consider the automorphism group of $\Delta$ as an abstract topological group, then $\Delta$ can still be recovered from this information up to first-order biinterpretability (Ahlbrandt+Ziegler). Recently, Bodirsky and Pinsker have shown that if we see the polymorphism clone of $\Delta$ as an abstract topological and algebraic structure, then we still know $\Delta$ up to primitive positive biinterpretability. It turns out that for many structures, in particular for some of the most prominent homogeneous structures, the topological structure of their automorphism group is determined by its algebraic structure; consequently, those structures can be recovered from the abstract group structure of their automorphism group up to first-order biinterpretability. We investigate when we can recover the topological structure of polymorphism clones from the algebraic laws which hold in them. Our investigations have their original motivation in theoretical computer science, more precisely in applications to Constraint Satisfaction Problems over homogeneous structures. These will be discussed in Manuel Bodirsky's talk.

 pinsker.pdf
Top

#### A. Pongrácz: The 42 reducts of the random ordered graph

We study a basic question in model theory: Given a structure F, what are the reducts of F, i.e., the structures with a first-order definition in F? If F is the dense linear order or the random graph, then there are five different structures definable from F, up to first-order interdefinability. Recently, the same notion was characterized for several other omega-categorical structures, such as the random tournament or the generic partially ordered set. I am going to talk about the classification of the reducts of the random ordered graph, and show that there are 42 of them up to first-order interdefinability. The techniques applied in the proof rely deeply on structural Ramsey theory.

This theorem can be considered as another instance of Simon Thomas' conjecture, which states that every countable homogeneous structure over a finite relational language has finitely many reducts up to first-order interdefinability.

 pongracz.pdf
Top

#### M. Sokic: Semilattices

We analyze the Ramsey property in the category of finite semilattices.

 sokic.pdf
Top

#### S. Solecki: Dual Ramsey theorem for trees

The classical Ramsey theorem was generalized in two major ways: to the dual Ramsey theorem by Graham and Rothschild (despite being a dual, it is a generalization) and to Ramsey theorems for trees initially by Deuber and Leeb. Bringing these two lines of thought together, I will present the dual Ramsey theorem for trees. In addition to presenting this concrete Ramsey result, I will outline the fragment of the abstract approach to Ramsey theory, developed earlier, that is needed in this concrete case.

 solecki.pdf
Top

#### S. Todorcevic: Forcing associated with homogeneous indivisible structures

In this joint work with M. Kurilic we investigate forcing notions associated with indivisible homogeneous structures. We obtain some forcing-factorization theorems in the case of the countable dense linear ordering and in the case of the random graph. We shall also relate our forcing-related classification results to some standard classification results in this area.

Top

#### T. Tsankov: On some generalizations of de Finetti’s theorem

A permutation group G acting on a countable set M is called oligomorphic if the action of G on $M^n$; has only finitely many orbits for each n. Those groups are well known to model-theorists as automorphism groups of omega-categorical structures. In this talk, I will consider the question of classifying all probability measures on $[0, 1]^M$invariant under the natural action of the group G. A number of classical results in probability theory due to de Finetti, Ryll-Nardzewski, Aldous, Hoover, Kallenberg, and others fit nicely into this framework. I will describe a couple of new results in the same spirit and a possible approach to carry out the classification in general.

Top

#### A. Vershik: The nonstandardness in the deterministic and random dynamics, and in combinatorics

Abstract: The standard dyadic filtration (= decreasing sequence of sigma-fields) is the simplest possible filtration -- the sigma fields of past of Bernoulli scheme. Soon after the construction (by the speaker in '70) of the ergodic dyadic filtrations which are not isomorphic to standard filtrations, it became clear that nonstandardness is an important general notion which occurs in many situations, like various kinds of dynamics, combinatorics, etc. The main facts -- lacunary theorem, the criteria of standardness towers of measures, entropy -- will be explained, together with a list of examples. The recent investigations of the filtrations generated by graded graphs give a possible link with the theory of $AF C^*$-algebras and with universal objects in model theory. Reasonable classification problems in measurable and Borel categories will be mentioned.

Top

#### P. Wesolek: Conjugacy classes in locally compact subgroups of S∞

Many closed subgroups of S∞ admit a comeagre conjugacy class. For example, S∞ (folklore) or $Aut(\mathbb{Q},<)$ (Truss) admit a comeagre conjugacy class. Kechris and Rosendal ask if a locally compact subgroup of S∞ can admit a comeagre conjugacy class. We answer the question in the negative via an analysis of locally compact subgroups of S∞ with measure theoretic or topological conditions on a conjugacy class.

 wesolek.pdf