The following notes are from the Ramsey DocCourse in Prague 2016. The notes are taken by me and I have edited them. In the process I may have introduced some errors; email me or comment below and I will happily fix them.
Title: Functions on Homogeneous Ramsey Structures 3 (of 3).
Lecturer: Michael Pinsker.
Date: Friday October 14, 2016.
Main Topics: Proof of Ramsey claim for canonical functions, Thomas’ Theorem for the Rado Graph, Open questions
Definitions: No new definitions
In the second lecture we saw a proof of Cameron’s theorem which characterizes the closed supergroups of . The proof was complete except for a Ramsey claim inside a proposition about canonical functions. We will complete Cameron’s theorem by proving that claim.
After that we will look at characterizing the closed supergroups of the automorphism group of the Rado graph. We focus on motivation.
Finally we discuss some open problems, research projects and good exercises.
The proof of the Ramsey claim
Here is the proposition about canonical functions that we used.
Proposition. Let be an ordered, Ramsey, homogeneous, -categorical structure, and assume that is -categorical.
Let . Fix finitely many constants .
There is a function such that and is canonical (from to ).
This is the Ramsey claim that we still need to show.
Proof of claim. Let be as in the assumptions of the proposition.
Throughout this proof we will conflate an -tuple with the the structure formed by . This correspondence can be done because is ordered (really we only need rigid).
Note that induces a (possibly infinite) colouring on by assigning .
A small fix will break this up into infinitely many (finite) colourings .
Enumerate the types of tuples in as . For define . These are each finite colourings since is -categorical.
Using Ramsey for we have that such that and is constant. In fact, through repeated applications of Ramsey, we can get that finitely many colourings are each constant.
Now fix a finite . Pick an so that all types of injective tuples in appear among . Now we can find an such that is constant on for each . This means that the function (on ) sends types to types, so it is canonical (on ).
It is worth pointing out that we snuck in a serious exercise without proof.
This was first proved in KPT using topological groups and the machinery of extreme amenability. Later on Sokic provided an (unpublished) purely combinatorial proof.
It is also worth noting that the entire canonical proposition can be proved using topological groups. This will appear in a paper soon.
Closed supergroups of the automorphism group of the Rado graph
We will now examine the question of what closed groups are there such that , where is the Rado graph. Unlike in the case of Cameron’s theorem, we do not know the groups ahead of time. We will walk through ways of discovering these groups. This is not an algorithm, but it does provide some insight.
- What can canonical maps do to the types?
- What canonical maps witness those type permutations?
- Repeat the first two questions after adding constants to the language.
- Try to show this is all of the canonical maps. Add any new ones you find to your list
Induced maps on types
Remember that every canonical function induces a map on the types. We will investigate the behaviour of these induced maps first.
In the case of the Rado graph this says that canonicity is determined by the behaviour of functions on pairs. More precisely:
Fact. Let be a function where is homogeneous in an -ary language with .
is canonical if and only if is canonical on all -tuples.
In the case of the Rado graph , so we only need to ask where the induced map sends and (where if there is no edge between and ).
The following table captures the four options:
Can these behaviours be captured by canonical permutations?
The next step is to look at these four classes of type permutations (really just type maps) and see which ones have vertex permutations that induce these maps. First we just look for any injections that induce these type maps.
It will be useful to recall that the Rado graph contains a copy of every countable graph (not just finite graphs).
For (1), find a copy of in and maps the vertices injectively into it. This will send all pairs to edges. For (2) we do the same thing except embed into a countable independent set.
So we know that these behaviours are attainable by embeddings, but can they be achieved via a vertex permutation? In the case of (1) and (2) we see that the answer is “no”, because the image of a vertex permutation will always have an edge (so not case 2) and a non-edge (not case 1). Therefore these cases won’t add any new closed supergroups.
For case (3), these will just be local automorphisms, or in the case of vertex permutations, full automorphisms. This also doesn’t add any new groups.
For case (4), we note that . One way to see this is that they have the same one-point extension property. Thus case (4) can be achieved by a vertex permutation. Call one of these maps an anti-isomorphism. Note that if we had tried the same trick as in (1) – finding a proper copy of – then we would only know that this behaviour was achievable by a vertex embedding. That wouldn’t tell us that the behaviour could be reached by a vertex permutation.
So far our only interesting group is the one generated by and an anti-isomorphism.
Our next step is to add constants and ask the same questions. Let’s look at the Rado Graph augmented by a point: .
Consider the sets and . These two sets partition .
Using this fact we can fix and exchange and via an isomorphism (from to ). We’ll call this map a swap.
How do we check that this is everything?
At this stage we might have a feeling that we have all the groups. To show that these are everything, we’ll start with a closed group that contains , a swap and an anti-isomorphism. We’ll also assume that contains more than just the closure of these three things.
In this case it will be enough to show that contains the map described in (1): a map . If then (this is an easy exercise).
Wait. Does our Ramsey proposition even apply?
A keen observer will notice that our Ramsey proposition requires that the Rado graph be a Ramsey structure, and we know that graphs do not form a Ramsey class (see Bootcamp 4). This means that we can’t apply the proposition directly. Also, the Rado graph isn’t ordered! Another reason why it doesn’t apply.
There are two solutions to this.
We know that graphs are edge-Ramsey (see Bootcamp 6) and this is actually enough Ramsey to prove the proposition for this case. This is not a “good” solution, because it relies very heavily on the graph structure. It doesn’t generalize well to other classes.
A better solution is to expand to a Ramsey class. In this case we look at ordered graphs. Equivalently we look at the Rado graph imbued with a linear order isomorphic to . This makes the mechanisms of the classification proof more difficult, but it’s not terrible.
Open questions and research projects
The previous observation leads to the following open question:
Question. Does every structure have a Ramsey expansion?
Assuming -categorical, the answer is “No”. We will see this in a later lecture.
Assuming it is homogeneous in a finite relation language, the question is open.
The Ramsey proposition we used is interesting. How much Ramsey does it encompass? More precisely:
The following is not an open question, but is a good exercise for someone trying to understand the definitions.
Exercise. Assume for all . Show the Ramsey proposition for .
What does canonical even mean here?
The question of classification also makes sense for structures with infinite languages, such as homogeneous metric spaces. An introduction to the Urysohn space can be found here.