Schedule for: 15w5100 - Homogeneous Structures

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

I will present the Ramsey theoretic statements (and hopefully say a bit about their proofs), which we proved in a joint work with Dana Bartosova, to obtain theorems about the dynamics of the homeomorphism group of the Lelek fan. One of the theorems is a generalization of the finite Gowers' Ramsey theorem.

This is joint work separately with Miodrag Sokic and Marcin Sabok. Given a Fraisse class, there are the related combinatorial questions: "Does this class have the Hrushovski property?" and "Is the automorphism group of the Fraisse limit an amenable group?". Building on work of Angel-Kechis-Lyons and Zucker the amenability question has recently been answered for all Fraisse classes of directed graphs, and using a Mackey-type construction the Hrushovski question has recently been answered for the same classes. We will survey the results and the techniques used.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. Please don't be late, or you will not be in the official group photo! The photograph will be taken outdoors so a jacket might be required.

We will consider Ramsey objects and objects of finite Ramsey degree in a Fraisse class K. We will show that an element of K is a Ramsey object if and only if a certain collection of ultrafilters is nonempty, also providing a similar characterization of having finite Ramsey degree. Time permitting, we will discuss applications to the dynamics of the automorphism group of the Fraisse limit.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

I will give a biased and partial survey of what can be gained by approaching a Polish group as the automorphism group of a homogeneous metric structure. In particular, I will discuss the definition and use of metric Fraïssé limits and the natural topometric structure on the automorphism group of a metric structure.

The Poulsen simplex is the unique metrizable Choquet simplex with dense extreme boundary. I will explain how one can study the Poulsen simplex from the perspective of Fraisse theory for metric structures, and how many classical results about the Poulsen simplex can be recovered in this framework. I will conclude by mentioning how this point of view allows one to define and construct the noncommutative analog of the Poulsen simplex.

It is well-known that the automorphism group of an omega-categorical structure encodes all model-theoretic information about the structure. Recently, an interesting correspondence has been discovered between properties of the theory (stability, omega-stability, NIP) and classes of Banach spaces on which certain dynamical systems (the automorphism group acting on type spaces over the model) can be represented. In the stable case, those dynamical systems also carry the structure of a semigroup that can be exploited. I will discuss what is known about this correspondence as well as some open questions. This is joint work with Itaï Ben Yaacov and Tomás Ibarlucía.

The pseudoarc is a remarkable compact connected space, in fact, it is the generic compact connected space. I will explain the connection between the pseudoarc and projective Fraisse limits coming for joint work with Trevor Irwin---the pseudoarc is represented as a quotient of such a limit. Further, I will describe recent work with Todor Tsankov, in which we determine the correct partial homogeneity of the projective Fraisse limit associated with the pseudoarc. This determination involves combinatorial and basic "dual" model theoretic arguments (e.g., a notion of dual type). I will also describe a transfer theorem, through which we recover Bing's homogeneity of the pseudoarc from our partial homogeneity of the projective Fraisse limit. Time allowing, I will also present recent work with Aristotelis Panagiotopoulos on the Menger curve viewed as a quotient of another projective Fraisse limit.

In this talk we present a way to reinterpret the Kechris-Pestov-Todorčević correspondence in an abstract categorical setting. We then instantiate this abstract setting in several ways. The interpretation in the category of countable structrures with embeddings will give us the well-known resutls of K-P-T theory for Fraïssé limits. The interpretation of this setting in categories of arbitrary structures with embeddings yields some recent results of Barto\v sova in which extreme anemability of automorphism groups of some uncounable structures was established. Finally, the interpretation in op-categories yields duals of some results of K-P-T theory. For example, we shall show that if $F$ is a projectively homogeneous structure, then $Aut(F)$ is extremely amenable if and only if the projective age of $F$ has the dual Ramsey property.

We will describe category-theoretic framework for Fraïssé limits, capturing objects outside of model theory. Our basic setting is a category enriched over metric spaces plus a function measuring the ``distortion" of arrows. Within this scheme, adding some natural axioms the Fraïssé limit exists, is unique, and has similar properties to classical Fraïssé limits. Our approach is parallel to Ben Yaacov's continuous Fraïssé theory, trying to avoid model-theoretic issues. Within our framework we capture the Gurarii space, the pseudo-arc, the Poulsen simplex, and some other objects coming from analysis and topology (both new and existing ones).

In general partition properties of homogeneous structures are properties of their automorphism group. As it is difficult to characterize homogeneous structures it might be better to try to obtain partition results for subgroups of the symmetric group directly instead of for homogeneous structures. Notions and results and unresolved issues arising in this context will be discussed.

Joint work wih Claude Laflamme, Norbert Sauer and Robert Woodrow. Two structures are said to be $\textit{equimorphic}$ if each embeds into the other. I will report on two conjectures about the number of structures (counted up to isomorphy) which are equimorphic to a given structure; one by Bonato and Tardif asking whether the number of trees equimorphic of a given tree is either $1$ or is infinite, the other by Thomass'e asking a similar question for relational structures. I will present a positive answer of Thomass'e's conjecture for chains and for countable homogeneous structures (whose automorphism group is oligomorphic). I will conclude by some results about the hypergraph of copies of a countable homogeneous structure.

Using Hrushovski’s predimension construction, we show that there exists a countable, $\omega$-categorical structure $M$ with the property that if $H$ is an extremely amenable subgroup of the automorphism group of $M$, then $H$ has infinitely many orbits on $M^2$. In particular, $H$ is not oligomorphic. This answers a question raised by several authors (including Bodirsky, Pinsker, Tsankov and Ne\v set\v ril). It follows that there is a closed, oligomorphic permutation group $G$ whose universal minimal flow $M(G)$ is not metrizable.

A primitive Jordan structure is a structure which has an automorphism group which is a primitive Jordan group. This means that the automorphism group acting on M is a Jordan group which preserves no non-trivial, proper equivalence relations on M. I will give a brief survey of examples where results on Jordan groups have been used to obtain results about reducts of primitive Jordan structures. In particular, I will discuss the classification of reducts, up to interdefinability, of any relatively 2-transitive semilinear ordering.

A countable relational structure $M$ is called $\textit{set-homogeneous}$ if whenever two finite substructures $U$, $V$ of $M$ are isomorphic, there is an automorphism of $M$ taking $U$ to $V$ (but we do not require that every isomorphism between $U$ and $V$ extends to an automorphism). This notion was originally introduced by Fraïssé, although unpublished observations had been made on it earlier by Fraïssé and Pouzet. Clearly every homogeneous structure is set-homogeneous. It is also not too difficult to construct examples of structures that are set-homogeneous but not homogeneous. It is natural to investigate the extent to which homogeneity is stronger than set-homogeneity, and this question has received some attention in the literature. For instance, it was shown by Ronse \cite{Ronse1978} that any finite set-homogeneous graph is in fact homogeneous. In this talk I will give a survey of some of the known results in this area, including results on countably infinite set-homogeneous graphs due to Droste, Giraudet, Macpherson and Sauer \cite{dgms}, and results on set-homogeneous directed graphs obtained in recent joint work with Macpherson, Praeger and Royle \cite{gmpr}. I will also present a number of interesting conjectures and open problems that remain about set-homogeneous structures.

(joint work with Aisha Abogatma) Previously a rather short list of countable homogeneous lattices was known, including, apart from the one-point lattice and the rationals, the countable universal-homogeneous distributive lattice and one or two others arising from amalgamations of certain classes of lattices. We show that there are in fact uncountably many countable homogeneous lattices. Our examples are all non-modular, and the natural question to ask is whether every countable homogeneous modular lattice is necessarily distributive, a conjecture which has recently been proved by Christian Herrmann. Our method also applies to show that certain other classes of structures also have uncountably many countable homogeneous members.

Many well known examples of homogeneous metric spaces and graphs can be viewed as analogs of the rational Urysohn space (for example, the random graph as the Urysohn space with distances {0,1,2}). In 2007, Delhomme, Laflamme, Pouzet, and Sauer characterized the countable subsets S of nonnegative reals for which an ``S-Urysohn space" exists. Sauer later showed that, under mild closure assumptions on S, the existence of the S-Urysohn space is equivalent to associativity of a natural binary operation on S induced by usual addition of real numbers. In this talk, I consider the R-Urysohn space, where R is an arbitrary ordered commutative monoid. I will first construct an extension R* of R, such that any model of the theory of the R-Urysohn space (in a discrete relational language) can be given the structure of an R*-metric space. I will then characterize quantifier elimination in this theory by continuity of addition in R*. Finally, I will characterize various model theoretic properties of the R-Urysohn space using natural algebraic properties of R.

Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subparts. In this talk we present joint work with Malliaris, in which we reprove their theorem using many of the same ideas, but with the key model theoretic ingredient of first determining the so-called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds, and offers a different structural perspective on the graphs in question.

A directed graph is connected-homogeneous if any isomorphism between every two finite connected subdigraphs extends to an automorphism of the digraph. In this talk we discuss the the classification of the countable such digraphs. This includes a description of the main classes of these digraphs as well as a discussion of the main steps in the proof of the classification. In the end we give arguments that show that their classification is on the one hand complete but on the other hand still incomplete.

A simple form of Ramsey's theorem says that for any positive integer $m$, there exists an $n=R(m)$ so that no matter how the pairs of an $n$-set are partitioned into two colours, some $m$-subset has all its pairs the same colour. In terms of graphs, this says if the edges of a $K_n$ are 2-coloured, a monochromatic copy of $K_m$ (as a subgraph) can always be found. Such a statement is often expressed in ``Ramsey arrow'' notation. A short survey of Ramsey arrows for graphs is given, culminating in a characterization found with Rodl and Sauer of those triples $G,H,r$ for which there is an $F$ that arrows $G$ when colouring $H$s with $r$ colours.

Homogeneous structures and their reducts have been used as templates of Constraint Satisfaction Problems (CSPs) to model qualitative reasoning problems in Artificial Intelligence. But this is not the only context in which homogeneous structures arise naturally in CS; we will discuss more recent links between homogeneous structures and permutation pattern avoidance classes, and between homogeneous structures and automata theory (for data word languages). I will present a fragment of existential second-order logic such that the queries that can be formulated in this logic describe (finite unions of) CSPs for reducts of homogeneous structures. This logic is quite powerful and contains MMSNP and most CSPs that have been studied in temporal and spatial reasoning.

Two omega-categorical structures are first order bi-interpretable iff their automorphism groups are isomorphic as topological groups. For a lot of well-known omega-categorical structures this statement still holds if we ignore the topology. But in 1990 Evans and Hewitt constructed two omega-categorical structures with isomorphic, but not topologically isomorphic automorphism groups. Similarly two omega-categorical structures are primitive positive bi-interpretable iff their polymorphism clones are topologically isomorphic. Basing on the group-counterexample we were able to construct a counterexample for the clones. This is a joint work with Manuel Bodirsky, David Evans and Michael Pinsker.

There has been a conjectured criterion, by Manuel Bodirsky and myself, for when deciding the truth of a primitive positive sentence over a reduct of a finitely bounded homogeneous structure is tractable. This criterion has recently been replaced by a seemingly better criterion, although the equivalence of the two criteria is an open problem. We discuss the two conjectures, their relation, and further related conjectures and thoughts.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.