Functions on Homogeneous Ramsey Structures 3 – Ramsey DocCourse Prague 2016 – Mike Pawliuk

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

Lecture 1 – Lecture 2 – Lecture 3

Introduction

In the second lecture we saw a proof of Cameron’s theorem which characterizes the closed supergroups of $\text{Aut}(\mathbb{Q}, <)$ . 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 $\Delta$ be an ordered, Ramsey, homogeneous, $\omega$ -categorical structure, and assume that $\Lambda$ is $\omega$ -categorical.

Let $f: \Delta \longrightarrow \Lambda$ . Fix finitely many constants $c_1,\ldots, c_n \in \Delta$ .

There is a function $g \in \overline{\{\beta f \alpha : \alpha \in \text{Aut}(\Delta), \beta \in \text{Aut}(\Lambda)\}}$ such that $g \upharpoonright \{c_1, \ldots, c_n\} = f \upharpoonright \{c_1, \ldots, c_n\}$ and $g$ is canonical (from $(\Delta, c_1, \ldots, c_n)$ to $\Lambda$ ).

This is the Ramsey claim that we still need to show.

Claim. $\forall F \subseteq (\Delta, c_1, \ldots, c_n)$ finite, there is an $F^\prime \subseteq (\Delta, c_1, \ldots, c_n)$ such that $F^\prime \cong F$ such that $f \upharpoonright F^\prime$ is canonical.

Proof of claim. Let $\Delta, \Lambda, f, c_1,\ldots, c_n$ be as in the assumptions of the proposition.

Throughout this proof we will conflate an $n$ -tuple $\overline{a} \in \Delta^n$ with the the structure formed by $\overline{a}$ . This correspondence can be done because $\Delta$ is ordered (really we only need rigid).

Note that $f$ induces a (possibly infinite) colouring $\chi$ on $\Delta^n$ by assigning $\chi(\overline{a}) = \text{type}_\Lambda (f \overline{a})$ .

A small fix will break this up into infinitely many (finite) colourings $\chi_i$ .

Enumerate the types of tuples in $(\Delta, c_1, \ldots, c_n)$ as $t_i, i \in \omega$ . For $i \in \omega$ define $\chi_i = \chi \upharpoonright \{\text{ tuples of type }t_i \}$ . These are each finite colourings since $(\Delta, c_1, \ldots, c_n)$ is $\omega$ -categorical.

Using Ramsey for $(\Delta, c_1, \ldots, c_n)$ we have that $\forall F \text{ finite }, \exists F^\prime$ such that $F \cong F^\prime$ and $\chi_i \upharpoonright F^\prime$ is constant. In fact, through repeated applications of Ramsey, we can get that finitely many colourings $\chi_i$ are each constant.

Now fix a finite $F$ . Pick an $n$ so that all types of injective tuples in $F$ appear among $t_0, \ldots, t_n$ . Now we can find an $F^\prime \cong F$ such that $\chi_i$ is constant on $F^\prime$ for each $0 \leq i \leq n$ . This means that the function $f$ (on $F$ ) sends types to types, so it is canonical (on $F$ ).

It is worth pointing out that we snuck in a serious exercise without proof.

Proposition. If $\Delta$ is a homogeneous Ramsey class, then $(\Delta,c_1, \ldots, c_n)$ is a Ramsey class.

This was first proved in KPT using topological groups and the machinery of extreme amenability. Later on Sokic provided an (unpublished) purely combinatorial proof.

Exercise. Prove the above proposition combinatorially. Assume any additional properties of $\Delta$ .

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 $H$ are there such that $\text{Aut}(R) \leq H \leq \text{Sym}(V)$ , where $R = (V,E)$ 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 $f$ induces a map on the types. We will investigate the behaviour of these induced maps first.

Fact. If $\Delta$ is homogeneous, then $\text{type}_\Delta(\overline{a})$ is determined by the relations on $\overline{a}$ .

In the case of the Rado graph this says that canonicity is determined by the behaviour of functions on pairs. More precisely:

Fact. Let $f:\Delta \longrightarrow \Lambda$ be a function where $\Delta$ is homogeneous in an $m$ -ary language with $m \geq 1$ .

$f$ is canonical if and only if $f$ is canonical on all $m$ -tuples.

In the case of the Rado graph $m=2$ , so we only need to ask where the induced map sends $E$ and $\perp$ (where $v \perp w$ if there is no edge between $v$ and $w$ ).

The following table captures the four options:

	$E$	$\perp$
1	$E$	$E$
2	$\perp$	$\perp$
3	$E$	$\perp$
4	$\perp$	$E$

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 $R$ contains a copy of every countable graph (not just finite graphs).

For (1), find a copy of $K_\omega$ in $R$ 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 $(V,E) \cong (V, \perp)$ . 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 $(V,\perp)$ – 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 $\text{Aut}(R)$ and an anti-isomorphism.

Adding constants

Our next step is to add constants and ask the same questions. Let’s look at the Rado Graph augmented by a point: $(V,E,c)$ .

Consider the sets $E_c = \{x \in V : cEx\}$ and $N_c = \{x \in V\setminus\{c\} : c\perp x\}$ . These two sets partition $V\setminus\{c\}$ .

Exercise Show that the graphs induced by $E_c$ and $N_c$ are both isomorphic to $R$ .

Using this fact we can fix $c$ and exchange $E_c$ and $N_c$ via an isomorphism (from $E_c$ to $N_c$ ). 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 $H \leq \text{Sym}(V)$ that contains $\text{Aut}(R)$ , a swap and an anti-isomorphism. We’ll also assume that $H$ contains more than just the closure of these three things.

In this case it will be enough to show that $\overline{H}$ contains the map described in (1): a map $e_E: V \longrightarrow K_\omega$ . If $e_E \in \overline{H}$ then $H = \text{Sym}(V)$ (this is an easy exercise).

Theorem (Thomas). These are all of the closed supergroups of $\text{Aut}(G)$ . You can add an anti-isomorphism, a swap, or both.

Exercise. Create a detailed proof of this theorem. A full proof is probably not more than about 4 pages.

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 $(\mathbb{Q}, \leq)$ . 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 $\omega$ -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:

Open question. Suppose that $\Delta$ is a homogeneous, ordered class that satisfies the Ramsey proposition. Is it true that $\Delta$ must be a Ramsey class?

The following is not an open question, but is a good exercise for someone trying to understand the definitions.

Exercise. Assume $\Delta^n \longrightarrow \Lambda$ for all $n$ . Show the Ramsey proposition for $f: \Delta^n \longrightarrow \Lambda$ .

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.

Open question. What are the closed supergroups of $\text{Aut}(\mathbb{U}_\mathbb{Q})$ or $\text{Aut}(\mathbb{U})$ , where these are the Urysohn space and the Uryoshn space with rational distances?

2 thoughts on “Functions on Homogeneous Ramsey Structures 3 – Ramsey DocCourse Prague 2016”

Pingback: Functions on Homogeneous Ramsey Structures 2 – Ramsey DocCourse Prague 2016
Pingback: Functions on Homogeneous Ramsey Structures 1 – Ramsey DocCourse Prague 2016