I’m just back from a very interesting few days at the 2nd Workshop on Homogeneous Structures in Prague.
The first workshop was in Leeds last year, and I wrote a post describing what was, for me, the highlight: Anatoly Vershik on his construction with Fedor Petrov of an exchangeable measure concentrated on Henson’s universal triangle-free graph, and Cameron Freer and Rihanna Patel on their extension of this, with Nate Ackermann, to essentially arbitrary countable structures with trivial algebraic closure.
This time, what most impressed me was the extent to which the theorem of Kechris, Pestov and Todorcevic has moved into the mathematical mainstream. This seems like a good place to describe the theorem, some extensions, and what it has recently been used before.
Fraïssé’s Theorem is the starting point of this, and indeed of any discussion of homogeneous structures. I will restrict myself to relational structures such as graphs and orders here, though there is important work in a much more general context. A structure M is homogeneous if any isomorphism between finite induced substructures can be extended to an automorphism of the entire structure. To understand this, you might like to show that the pentagon, or 5-cycle graph, is homogeneous. However, the hexagon, or 6-cycle, is not: a pair of points two steps apart and a pair three steps apart are isomorphic as induced subgraphs but are not equivalent under automorphisms of the whole graph.
The age of a relational structure is the class of finite structures which can be embedded in it. It is easy to see that the age of a relational structure M is closed under isomorphism, closed under taking induced substructures, and has the joint embedding property: for any two structures in the age, there is a structure which embeds both of them. Moreover, if M is at most countable, then its age has at most countably many members up to isomorphism. These properties characterise ages of countable structures.
For homogeneous structures, there is an extra condition, the amalgamation property. This asserts that, if two structures B1 and B2 have a common substructure A, then they can be simultaneously embedded in a structure in the age such that the copies of A coincide. The age of a homogeneous structure satisfies this condition. Moreover, Fraïssé’s theorem asserts that a class satisfying the conditions of the preceding paragraph and the amalgation property is the age of a countable homogeneous structure, unique up to isomorphism. Such a class is called a Fraïssé class, and the countable homogeneous structure is called the Fraïssé limit of the class.
Examples of countably infinite homogeneous structures are the rational numbers as ordered set (the age consists of all finite ordered sets) and the the random graph (the age consists of all finite graphs).
A class C has the Ramsey property if, for any two structures A and B in C, and any positive integer r, there exists a structure C in C such that, if the substructures of C isomorphic to A are coloured with r colours, there is a substructure isomorphic to B such that all its A-substructures have the same colour. In the case where C consists of sets with no structure, this property holds, and is the classical form of Ramsey’s theorem.
The final ingredient is the following. The automorphism group of a countable structure M is a topological group, with the topology of pointwise convergence. Now a flow for a topological group G is a continuous action of G on a compact Hausdorff space. We say that G is extremely amenable if every flow for G has a fixed point. More generally, any group has a universal minimal flow: it is extremely amenable if the universal minimal flow is a space with a single point.
Now the theorem of Kechris, Pestov and Todorcevic says:
The age of a countable homogeneous structure with a total order is a Ramsey class if and only if its automorphism group is extremely amenable.
This was a remarkable and unexpected result bringing together homogeneous structures, Ramsey theory and topological dynamics. The first and most important example of a homogeneous structure with this property is the countable dense linear order without endpoints (aka the rational numbers as ordered set).
So what were some of the new directions for this theory? Here are some brief summaries.
- Lionel Nguyen Van Thé showed that a Fraïssé class of structures has an expansion (obtained by adding extra relations) with the Ramsey property if and only if the automorphism group of its Fraïssé limit has an extremely amenable subgroup with precompact quotient.
- For the symmetric group of countable degree, the Glasner–Weiss theorem states that the universal minimal flow is the action on the class of linear orders of the countable set. Todor Tsankov gave a complete classification of the minimal flows for this group. Curiously, the arguments required for this classification had been done by Claude Frasnay in the 1960s, in a completely different context. I had been aware of Frasnay’s work because it was related to my very first theorem on infinite permutation groups, the analogue of the Livingstone–Wagner theorem for finite groups: a classification of groups which are transitive on n-sets for all n but fail to be n-transitive (i.e. transitive on n-tuples of distinct elements) for some n.
- Manuel Bodirsky used KPT-type methods, among other things, to prove a dichotomy (asserting that such problems are either polynomial-time or NP-complete) for constraint satisfaction problems based on reducts of the universal C-relation. This is the homogeneous structure whose age consists of the sets of leaves of binary trees, with a ternary relation which holds for (x,y,z) if z branches off from x and y earlier than they branch from one another. Special cases of such problems have been considered by mathematical biologists because of their applications in phylogeny. Moreover, he has a conjecture that similar methods will apply for all constraint satisfaction problems based on oligomorphic structures.
There were many more beautiful talks; I would just like to mention Michael Pinsker’s talk, on joint work with Manuel Bodirsky. He announced the title “TBA” which, on this occasion, stood for “Topological Birkhoff and Applications”. A classical theorem of Birkhoff says that, if A and B are finite algebrasi with the same signature, then B satisfies all of the identities of A if and only if B is a homomorphic image of a subalgebra of a finite product of copies of A. This is false for infinite algebras – in general one needs infinite products – but they have shown that it is true for oligomorphic algebras with a condition of continuity. [An algebra is oligomorphic if the semigroup of unary term functions it defines contains an oligomorphic group. Birkhoff’s theorem can be phrased in terms of the map taking any term function of A to the corresponding term function of B, and the extra requirement is that this homomorphism should be continuous, in the topology of pointwise convergence.] The result can also be phrased in terms of primitive positive bi-interpretability, if you are a model theorist. So “the complexity of the constraint satisfaction problem of a countably categorical structure depends only on its topological polymorphism clone”, which leads on to the theorem that Manuel Bodirsky presented.
A feast of interesting stuff, and I haven’t mentioned many interesting problems which arose. Slides should appear on the workshop web page sometime soon.
Sad to say, I had to leave before the meeting was over, for a completely unrelated reason. My daughter and her husband had managed to get tickets for the Olympic Games, but were unable to take my granddaughter Lyra along; so I had to come home to babysit Lyra. This was even more fun than the workshop …