Topological dynamics and Ramsey classes – Ramsey DocCourse Prague 2016

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: Topological dynamics and Ramsey classes.

Lecturer: Lionel Ngyuen Van Thé.

Date: November 14, 2016.

Main Topics: Proof of KPT correspondence between extreme amenability and ramsey class.

Definitions: Topological group, $S_\infty$, $d_R, d_L$, Polish group, ultrametric, $G$-flow, extreme amenability.


Introduction

Our main goal is to introduce the KPT correspondence and provide proofs of two main results. The flavour is combinatorial, but the techniques are topological. The KPT correspondence is a powerful bridge between Structural Ramsey Theory and Topological Dynamics.

Main References

Here are the main references for these lectures. We will provide other secondary references with each lecture.

Background about topological dynamics

A disclaimer that all spaces discussed will be Hausdorff spaces, so we will not mention it again.

Definition. A topological group $(G, \mathcal{T})$ is a group $G$ together with a topology $\mathcal{T}$ on $G$ such that multiplication and inversion are continuous.

Typically we will be looking at autmorphisms, or isomorphisms, or some other collection of bijections.

Example. Let $S_\infty :=$ the collection of all bijections on $\mathbb{N}$, together with the topology of pointwise convergence. That is, basic open sets are of the form $A(g,F) = \{h \in S_\infty : h \upharpoonright F = g \upharpoonright F\}$, where $F \subset \mathbb{N}$ is finite and $g \in S_\infty$.

This has some compatible metrics:

  1. $d_L (g,h) := 2^{-n}$, where $n := \min\{k \in \mathbb{N} : g(k) \neq h(k)\}$.
  2. $d_R (g,h) := d_L(g^{-1}, h^{-1})$.
  3. $d(g,h) := d_L(g,h) + d_R (g,h)$.
Definition. A topological space is Polish if it is separable and its topology is generated by a complete metric. A space is separable if it has a countable dense subset.

A metric space $(X, \rho)$ is an ultrametric space if
$$\forall x,y,z \in X \text{ we have }d(x,z) \leq \max\{d(x,y), d(y,z)\}.$$ dThis is a strong form of the triangle inequality.

Exercise. The following exercises are on the easy side.

  1. $d_L$ is left-invariant.
  2. $d_R$ is right-invariant.
  3. $d$ is neither left-invariant nor right-invariant.
  4. $S_\infty$ is a Polish group.
  5. Compute the completions of $d_L$ and $d_R$.
  6. $d$ is complete.
  7. $d_L$ and $d_R$ are ultrametrics.
  8. The balls of radius $2^{-m}$ give a finite partition of $(S_\infty, d_L)$ and $(S_\infty, d_R)$.

“What is happening today is really about completions; specifically $d_R$.”

The last exercise is partly why closed subgroups have nice interactions with respect to combinatorics.

The KPT machinery can be transposed into the Polish group setting, but requires continuous Fraïssé theory (which we will learn about in later talks).

Fact. The closed subgroups of $S_\infty$ are exactly those of the form $\text{Aut}(\mathbb{K})$, where $\mathbb{K}$ is a Fraïssé structure.
Definition. A continuous action of a topological group $G$ on a compact space $X$ is an algebraic action of $G$ on $X$ that is also continuous when seen as a map $G \times X \rightarrow X$ where $(g,x) \mapsto g \cdot x$.

A $G$-flow $G \curvearrowright X$ is a continuous action of $G$ on a compact space $X$.

A topological group $G$ is extremely amenable when every $G$-flow has a fixed point. That is there is a $x \in X$ such that $\forall g \in G$ we have $g \cdot x = x$.

We will not use the notion of amenability here, but to mention it: a group $G$ is amenable when every $G$-flow admits an invariant Borel probability measure. So in this way we see that extreme amenability implies amenability.

Exercise. Suppose that $G \curvearrowright X$ is a $G$-flow. Let $x \in X$. Show that $\overline{G \cdot x} := \text{topological closure}(\{g \cdot x : g \in G\})$ is a compact, $G$-invariant subspace of $X$ (i.e. $g \cdot y \in \overline{G \cdot x}$, when $g \in G$ and $y \in \overline{G \cdot x}$). That is, $G \curvearrowright \overline{G \cdot x}$ is a $G$-flow.

Flows of this form are very important, and we will investigate them in more detail in the second lecture.

The KPT correspondence

Here is the major correspondence between Ramsey properties and extreme amenability.

Theorem (Kechris-Pestov-Todorcevic, 2005). Let $\mathbb{K}$ be a Fraïssé structure such that elements of $\text{Age}(\mathbb{K})$ are rigid. The following are equivalent:

  1. $\text{Aut}(\mathbb{K})$ is extremely amenable.
  2. $\text{Age}(\mathbb{K})$ is a Ramsey class (for structures).

The proof will be self-contained. The right way to think about this might be to use more sophisticated topological notions from functional analysis. We will hint at these at the end of the lecture, then go into more detail in the following lectures.

Proof that $ 1\Rightarrow 2$

We use extreme amenability to prove the Ramsey property. We do this by constructing a compact $G$-flow, and then correctly interpreting what a fixed point is.

Proof of $1 \Rightarrow 2$.

Let $G = \text{Aut}(\mathbb{K})$. Fix $k \in \mathbb{N}$, $A,B \in \text{Age}(\mathbb{K})$. It suffices to show that $\mathbb{K} \longrightarrow (B)_k^A$. So fix a colouring $\xi: \binom{\mathbb{K}}{A} \longrightarrow [k]$. (You will probably forget about all these things, because we are going to leave them to the side for now. We’ll come back to them though!)

In order to use extreme amenability, we construct a compact space that $G$ acts on. Let $X$ be the collection of all $k$ colourings of $\binom{\mathbb{K}}{A}$. Specifically, $$X = [k]^\binom{\mathbb{K}}{A}$$ which is compact when given the product topology. $G$ acts on $X$ by permuting the copies of $A$, specifically $g \cdot \gamma (\tilde{A}) = \gamma(g^{-1}(\tilde{A}))$. The inverse is only there to ensure that it is an action; it is not mysterious.

Exercise. Show that this action is continuous.

Now applying extreme amenability to $X$ will be useless. We can already identify fixed points, namely constant colourings. Also, $X$ does not know anything about $\chi$. (Where $\chi$ was our original colouring. Did you forget about it?) So we go to a place that knows about $\chi$. We instead consider the $G$-flow $\overline{G \cdot \chi}$.

By extreme amenability, this has a $G$-fixed point. So there is a $\chi_0 \in \overline{G \cdot \chi}$ such that $\forall g \in G$ we have $g \cdot \chi_0 = \chi_0$.

By ultrahomogeneity of $\mathbb{K}$, $\chi_0$ is a constant colouring on $\binom{\mathbb{K}}{A}$. We can see that because for all $g \in G$ and all $\tilde{A} \in \binom{\mathbb{K}}{A}$ we have $\chi_0 (\tilde{A}) = \chi_0 (g^{-1} (\tilde{A}))$. Since there is also an automorphism of $\mathbb{K}$ that can map $A$ to a copy $\tilde{A}$, we have that $\chi_0$ is constant.

Now we are going to transfer this to knowledge about $\chi$. Note that $\binom{B}{A}$ is a finite subset of $\binom{\mathbb{K}}{A}$, so the values $\chi_0$ takes on this set specifies a basic open set $U$ in $X$. Since $\chi_0 \in \overline{G \cdot \chi}$, that means $U \cap (G \cdot \chi) \neq \emptyset$. Namely take $g$ to witness this.

Therefore $$\chi_0 \upharpoonright \binom{B}{A} = g \cdot \chi \binom{B}{A} = \chi \upharpoonright \binom{g^{-1}(B)}{A}.$$ Setting $\tilde{B} = g^{-1}(B)$ we have that $\chi \upharpoonright \binom{\tilde{B}}{A}$ is constant, as desired.

Proof that $ 2\Rightarrow 1$

To prove that a group is extremely amenable from the Ramsey property we will discretize $G$. We will prove a (discrete) Ramsey-type property in our setting, and a continuous, approximate version (using the discrete version). The continuous Ramsey version will allow us to approximate a fixed point arbitrarily well. By taking a limit, we will get a true fixed point.

Proof of $2 \Rightarrow 1$.

First we may assume that the domain of $\mathbb{K}$ is $\mathbb{N}$. Then let $A_m$ be the substructure of $\mathbb{K}$ supported by the domain $[m]$. (We used this same trick in Bootcamp 5, but there it was for compactness reasons.)

Since $A_m$ is rigid, the setwise stabilizer is the same as the pointwise stabilizer on $A_m$. That is $$\{g \in G : g(A_m) = A_m\} = \text{stab}(A_m).$$ Note that $\text{stab}(A_m)$ is a closed subgroup of $G$.

Correspondence. Every $[g] \in G/\text{stab}(A_m)$ is in correspondence with $g^{-1}(A_m) \in \binom{\mathbb{K}}{A}$.
Proof. Fix $g,h \in G$.

  • $\text{stab}(A_m) g = \text{stab}(A_m) h$
  • $\Leftrightarrow \text{stab}(A_m)gh^{-1} = \text{stab}(A_m)$
  • $\Leftrightarrow gh^{-1} \in \text{stab}(A_m)$
  • $\Leftrightarrow gh^{-1} \upharpoonright A_m = \text{id} \upharpoonright A_m$
  • $\Leftrightarrow h^{-1} \upharpoonright A_m = g^{-1} \upharpoonright A_m$
  • $\Leftrightarrow h^{-1}(A_m) = g^{-1}(A_m)$.

The last step used rigidity in the reverse implication.

Observe that $[g]$ is the $d_R$ ball of radius $2^{-m}$ around $g$. Recall that these balls give a finite partition of $G$.

We are now ready to state a discrete Ramsey-type result in this setting.

Discrete Ramsey. Let $m,k \in \mathbb{N}$, $F \in [G]^{<\omega} $. Suppose that $f: G \rightarrow [k]$ is constant on each equivalence class of $G/\text{stab}(A_m)$.

THEN there is a $g \in G$ such that $f$ is constant on $Fg = \{hg : h \in F\}$.

Proof. Consider the projection $[F] = \{[h] : h \in F\}$, which can be thought of as a finite collection of copies of $A$ (by the correspondence above). Find a $B \in \text{Age}(\mathbb{K})$ that contains all these copies, i.e. $[F] \subseteq \binom{B}{A}$. By the Ramsey property, there is a $\tilde{B} \in \binom{\mathbb{K}}{B}$ such that $f$ is constant on $\binom{\tilde{B}}{A}$.

By ultrahomogeneity, there is a $g \in G$ such that $\tilde{B} = g^{-1}(B)$. (We’ll use this in a moment.)

Now,

  • $[Fg] = \{[hg] : h \in F\}$
  • $= \{(hg)^{-1}(A_m) : h \in F\}$
  • $= \{g^{-1}\left(h^{-1}(A_m)\right) : h \in F\}$
  • $= g^{-1}\{h^{-1}(A_m) : h \in F\}$
  • $\subseteq g^{-1} \binom{B}{A}$
  • $=\binom{g^{-1}(B)}{A}$
  • $=\binom{\tilde{B}}{A}$

Since $f$ is constant on $\binom{\tilde{B}}{A}$, it must also be constant on $[Fg]$. Since $f$ was constant on each equivalence class, this means that $f$ is constant on $Fg$, as desired.

We will now establish a continuous version of this Ramsey property.

Continuous Ramsey. Let $\mathcal{F}$ be a finite family of functions $f_i : (G, d_R) \rightarrow \mathbb{C}$ that are uniformly continuous, bounded. Let $F \in [G]^{ 0$.

There is a $g \in G$ such that $\forall f \in \mathcal{F}$, $f$ is constant up to $\epsilon$ on $Fg$. That is, $$\forall h, h^\prime \in F, \vert f(hg) – f(h^\prime g) \vert < \epsilon.$$

Proof. This is left as an exercise. Start with a single function $f$. Use boundedness and $\epsilon$ to cut the range of $f$ into many tiny intervals. Think of $f$ as a step function. These intervals will be act as our colours.

Use uniform continuity to make sure that $f$ is constant on each equivalence class (use the fact about how $d_R$ creates partitions of $G$.)

Then apply the discrete Ramsey to the step function version of $f$. Unwinding what that means about the true $f$ will give the desired conclusion.

Now we are in a position to finish the original proof. We wish to show that $G$ is extremely amenable. So let $G \curvearrowright X$ be a $G$-flow.

Fix $F \in [G]^{\omega}$, $\mathcal{F}$ a finite familiy of functions $f_i : X \rightarrow \mathbb{C}$ that are uniformly continuous, bounded. (Note that the domain of these functions is different than the hypothesis of the continuous Ramsey fact. You might also wonder what uniform continuity means in this context. Don’t worry for now; we’ll fix that later.) Let $\epsilon >0$. Define $$E(F, \mathcal{F}, \epsilon) := \{x \in X : \forall h \in F, \forall f \in \mathcal{F}, \vert f(hx) – f(x) \vert < \epsilon \}.$$ This is the collection of all approximate fixed points.

This is a closed subset of $X$, and hence compact.

General topology fact. If $f: X \rightarrow \mathbb{C}$, and $x \in X$ is fixed, then the function $f_x : (G, d_R) \rightarrow \mathbb{C}$, where $f_x (g) = f(gx)$ is uniformly continuous and bounded.

In this way, for a $x \in X$, $\mathcal{F}$ transfers to $\mathcal{F}_x = \{f_x : f \in \mathcal{F}\}$, a collection of uniformly continuous, bounded functions from $(G, d_R)$ to $\mathbb{C}$.

Applying the continous Ramsey fact we see that every $E(F, \mathcal{F}, \epsilon)$ is non-empty, and these sets have the finite intersection property (finite nested such $E$ have non-empty intersection).

Since they are compact, we know that the full infinite intersection is nonempty. That is there is a $$x_0 \in \bigcap_{F, \mathcal{F}, \epsilon} E(F, \mathcal{F}, \epsilon).$$

Claim. $x_0$ is a fixed point of $G$.

Once we have this, the proof is finished.

Proof of claim. Assume there is a $g_0 \in G$ such that $g_0 x_0 \neq x_0$. Then, by Urysohn’s Lemma, there is an $f_0: X \rightarrow \mathbb{C}$ uniformly continuous, bounded, such that $1 = \vert f_0 (g_0 x_0) – f_0 (x_0) \vert$.

This contradicts the fact that $x_0 \in E(\{f_0\}, \{g_0\}, \frac{1}{3})$.

Observations and exercises

This proof is not technically difficult, but the picture is hard to see. We’ll give a broader picture in later lectures.

Let us play around with the use of rigidity. It was only used in one part of the proof (find it!).

Exercise. Asuume that $\mathbb{K}$ is Fraïssé.

  1. If $\text{Aut}(\mathbb{K})$ is extremely amenable, then the elements of $\text{Age}(\mathbb{K})$ are rigid.
  2. If $\text{Age}(\mathbb{K})$ is a Ramsey class, is $\text{Aut}(\mathbb{K})$ is extremely amenable? If not, find the correct Ramsey condition to make the proof work without rigidity.

The Ramsey property should be thought of as a natural notion of separation. It says that some functions cannot be separated.

Uniform structures

We introduce the concept of uniform structures. Broadly, a uniform structure is weaker than a metric structure, and is the weakest place where the notion of “uniform continuity” still makes sense. This will fix the issue that was present in the proof of $2 \Rightarrow 1$ where we used uniformly continuous functions from $X$ to $\mathbb{C}$. We made no assumption about the metrizability of the compact space $X$, but it will turn out that compact spaces always have a unique uniform structure (that agrees with its topology).

These nLab notes provide a good introduction to uniform spaces. (Mike: These notes are better written than I could do without a lot of work. It isn’t essential to understand uniform spaces to understand the arguments being used in these lectures.)

This entry was posted in Course Notes, Ramsey DocCourse Prague 2016 and tagged , , , , . Bookmark the permalink. Both comments and trackbacks are currently closed.

One Trackback