Introduction to the KPT correspondence 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: Introduction to the KPT correspondence 3 (of 3).

Lecturer: Lionel Ngyuen Van Thé.

Date: November 18, 2016.

Main Topics:

Definitions: Expansion property,

Lecture 1 – Lecture 2 – Lecture 3

Introduction

In the second lecture we saw that the Ramsey property of $\mathbb{K}^\star$ (a combinatorial property) ensures universality of a certain minimal flow (a dynamical property). Today we’ll look at going from a dynamical property (minimality) to a combinatorial property (the expansion property).

From last time

Recall that we proved the following in the second lecture:

Theorem (KPT 05, Nguyen Van Thé 13). Assume that $\mathbb{K}^\star$ is a precompact Ramsey expansion of $\mathbb{K}$ . Then $\text{Aut}(\mathbb{K}) \curvearrowright X^\star$ is universal for minimal $\text{Aut}(\mathbb{K})$ -flows.

Here
$\displaystyle X^\star := \overline{\text{Aut}(\mathbb{K}) \cdot \vec{R^\star}}.$

Last time we saw that precompactness of the expansion allows us to topologically identify
$\displaystyle \text{Aut}(\mathbb{K}) / \text{Aut}(\mathbb{K}^\star)\cong X^\star.$
We also saw that $X^\star$ is a subset of a large compact product
$\displaystyle P^\star := \prod_{i \in I} \{0,1\}^{\mathbb{N}^{a(i)}}.$

Our main question today will be “What combinatorial properties guarantee that $X^\star$ is a minimal flow?” More precisely, what condition must an expansion $\vec{R^\star} \in P^\star$ satisfy so that $X^\star$ is minimal.

Definitions

We start by reminding you about the expansion property (which we looked at in Bootcamp 4 and Bootcamp 7).

Definition. Let $L \subset L^\star$ be first order relational languages, $\mathcal{K}$ a class of finite $L$ -structures and $\mathcal{K}^\star$ a class of finite expansions of $\mathcal{K}$ in $L^\star$ .

We say that $\mathcal{K}^\star$ has the expansion property (EP) (relative to $\mathcal{K}$ ) when $\forall A \in \mathcal{K}, \exists B \in \mathcal{K}$ such that $\forall A^\star, B^\star \in \mathcal{K}^\star$ (expansions of $A,B$ respectively), we have $A^\star$ embeds in $B^\star$ .

When $\mathcal{K}$ has the Joint Embedding Property, then (EP) is equivalent to $\forall A \in \mathcal{K}, \forall A^\star \in \mathcal{K}^\star, \exists B \in \mathcal{K}$ such that $\forall B^\star \in \mathcal{K}^\star$ (an expansion of $B$ ), we have $A^\star$ embeds in $B^\star$ .

The major theorem relating minimality and (EP)

Here is the major theorem we will prove.

Theorem (KPT 05, Nguyen Van Thé 13). Let $\mathbb{K}$ be a Fraïssé structure, $\mathbb{K}^\star = (\mathbb{K}, \vec{R^\star})$ be a precompact expansion of $\mathbb{K}$ (not necessaily Fraïssé). The following are equivalent.

$\text{Aut}(\mathbb{K}) \curvearrowright X^\star$ is minimal.
$\text{Age}(\mathbb{K}^\star)$ has the (EP) relative to $\text{Age}(\mathbb{K})$ .

“You have to understand the purpose!” – Nešetřil.

“The difficulty is really translating into dynamical language what the combinatorics mean.” – Lionel

Before proving this theorem, we prove two propositions which will contain all the heavy lifting. For notational simplicity you may assume that $R^\star$ is just a single relation $R$ .

Proposition 1. For $\vec{S}, \vec{T} \in P^\star$ the following are equivalent.

$\vec{S} \in \overline{G \cdot \vec{T}}$ .
$\text{Age}(\mathbb{K}, \vec{S}) \subseteq \text{Age}(\mathbb{K}, \vec{T})$ .

Exercise. Give a proof of this.

Proposition 2. Given the same hypotheses of the major theorem, the following are equivalent.

$\text{Age}(\mathbb{K}^\star) \subseteq \text{Age}(\mathbb{K}, \vec{S})$ , for all $\vec{S} \in X(R):= \overline{G \cdot \vec{R^\star}}$ .
$\text{Age}(\mathbb{K}^\star)$ has the (EP) relative to $\text{Age}(\mathbb{K})$ .

“(2) is the correct finitization of (1).”

Proof of proposition 2. We first prove $(1) \Rightarrow (2)$ . Fix an $A^\star \in \text{Age}(\mathbb{K}^\star)$ . We will find a $B \in \text{Age}(\mathbb{K})$ that witnesses the (EP).

By (1), for all $\vec{S} \in X(R)$ we have $A^\star$ embeds into $(\mathbb{K}, \vec{S})$ . So there is a finite $C \subset \text{dom}(\mathbb{K})$ such that
$\displaystyle \vec{S} \in X_C := \{\vec{T} \in X(R) : A^\star \cong (\mathbb{K}, \vec{T}) \upharpoonright C\}$
which is open in $P^\star$ .

In this way $\{X_C : C \in [\text{dom}(\mathbb{K})]^{< \omega}\}$ forms an open cover of $X(R)$ .

By compactness, there are $C_1, \ldots, C_n$ finite such that $X(R) = \bigcup_{i \leq n} X_{C_i}$ .

Let $B$ be the finite substructure of $\mathbb{K}$ supported by $C = \bigcup_{i \leq n} C_i$ .

Claim: $B$ witnesses the (EP) for $A^\star$ .

This is all that remains to finish the proof that $(1) \Rightarrow (2)$ .

Proof of claim. Let $B^\star \in \text{Age}(\mathbb{K}^\star)$ be an expansion of $B$ . So there is an embedding $\phi: B^\star \rightarrow \mathbb{K}^*$ .

This induces an embedding $\phi^\prime : B \rightarrow \mathbb{K}$ . By ultrahogeneity (for $\mathbb{K}$ ) we can extend $\phi^\prime$ to an automorphism $g: \mathbb{K} \rightarrow \mathbb{K}$ .

Then, for $i \in I$ and $y_1, \ldots, y_{a(i)} \in B$ we have

$R_i^{B^\star} (y_1, \ldots, y_{a(i)})$
$\Leftrightarrow R_i^{\star} (g(y_1), \ldots, g(y_{a(i)}))$ , [Since $\phi$ preserves the $B^\star$ structure, and $g$ extends $\phi^\prime$ .]
$\Leftrightarrow g^{-1}(R_i^\star (y_1, \ldots, y_{a(i)}))$ , [by the definition of logic action].

So setting $S_i = g^{-1} R^\star$ for all $i \in I$ we get $B^\star \cong (\mathbb{K}, \vec{S}) \upharpoonright C$ .

Now $\vec{S} \in \bigcup_{i \leq n} X_{C_i}$ , so there is an $l \leq n$ such that $\vec{S} \in X_{C_l}$ .

So
$\displaystyle A^\star \cong (\mathbb{K}, \vec{S}) \upharpoonright C_l \leq (\mathbb{K}, \vec{S}) \upharpoonright C \cong B^\star.$
Thus $A^\star$ embeds into $B^\star$ .

We now prove $(2) \Rightarrow (1)$ . Fix $A^\star \in \text{Age}(\mathbb{K}^\star), B \in \text{Age}(\mathbb{K})$ witnessing the (EP).

Take an $\vec{S} \in X(R)$ . Then, by the (EP),
$\displaystyle A^\star \leq (\mathbb{K}, \vec{S}) \upharpoonright B \in \text{Age}(\mathbb{K}, \vec{S}).$
So $\text{Age}(\mathbb{K}^\star) \subseteq \text{Age}(\mathbb{K}, \vec{S})$ .

Proof of major theorem. Now we glue together proposition 1 and 2. Let $G = \text{Aut}(\mathbb{K})$ .

$G \curvearrowright X^\star$ is minimal,
$\Leftrightarrow \forall \vec{S} \in X(R)$ we have $\vec{R^\star} \in X(S)$
$\Leftrightarrow \forall \vec{S} \in X(R)$ we have $\text{Age}(\mathbb{K}^\star) \subseteq \text{Age}(\mathbb{K}, \vec{S})$ [Prop 1]
$\Leftrightarrow \text{Age}(\mathbb{K}^\star)$ has the (EP) relative to $\text{Age}(\mathbb{K})$ .

The corollary

We can now combine this with the result from the second lecture (which tells us about universality) to get the following method for computing universal minimal flows.

Theorem (KPT 05, Nguyen Van Thé 13). Let $\mathbb{K}$ be a Fraïssé structure, $\mathbb{K}^\star = (\mathbb{K}, \vec{R^\star})$ be a precompact Fraïssé expansion of $\mathbb{K}$ with (EP) and (RP). Then
$\displaystyle \text{Aut}(\mathbb{K}) \curvearrowright M(\text{Aut}(\mathbb{K})) = \text{Aut}(\mathbb{K}) \curvearrowright \overline{\text{Aut}(\mathbb{K}) \cdot \vec{R^\star}}.$

This gives an explicit, combinatorial way to compute a universal minimal flow. You only need to find a precompact expansion of $\mathbb{K}$ with (EP) and (RP). Often (RP) is used to prove (EP).

All of the universal minimal flows constructed in this way will be metrizable.

Examples

For the following groups, the universal minimal flow is the logic action on the space $\text{LO}(\mathbb{N})$ : $\text{Aut}(\mathbb{R}), \text{Aut}(H_n), \text{Iso}(\mathbb{U}_\mathbb{Q})$ . [See lecture 2 for definitions of these spaces.]
For the following groups, the universal minimal flow is the logic action on the space of “natural orders” (the ones that respect the linear orders “favoured” by the structure): $\text{Aut}(\mathbb{B}_\infty), \text{GL}(F^{< \omega})$ (for $F$ a finite field).
For $\text{Aut}(K_{\omega, \omega})$ , the universal minimal flow is the logic action on convex linear orders on $K_{\omega,\omega}$ .

“Converses” to the corollary

The following captures the uniqueness of a precompact expansion.

Theorem (KPT 05, Nguyen Van Thé 13). Let $\mathbb{K}$ be a Fraïssé structure, $\mathbb{K}^\star = (\mathbb{K}, \vec{R^\star})$ be a precompact Fraïssé expansion of $\mathbb{K}$ . If $\text{Aut}(\mathbb{K}) \curvearrowright \overline{\text{Aut}(\mathbb{K}) \cdot \vec{R^\star}}$ is the universal minimal flow, then $\mathbb{K}^\star$ has the (EP) and the (RP).

We saw in lecture 2 that the “smallness” of the universal minimal flow is dictated partly by the homogeneity and Ramsey properties of the group. The following theorem captures that notion.

Theorem (Melleray-Nguyen Van Thé-Tsankov, 2016). Let $\mathbb{K}$ be a Fraïssé structure. The following are equivalent.

$M(\text{Aut}(\mathbb{K}))$ is metrizable with a $G_\delta$ orbit.
$\mathbb{K}$ admits a precompact expansion $\mathbb{K}^\star$ that is Fraïssé and has the (EP) and the (RP).

Why metrizability? It is a reasonable “smallness” condition.

This was expanded by Zucker, and he was able to drop the $G_\delta$ condition, while capturing the Ramsey degree.

Theorem (Zucker 2016). Let $\mathbb{K}$ be a Fraïssé structure. The following are equivalent.

$M(\text{Aut}(\mathbb{K}))$ is metrizable.
$\mathbb{K}$ admits a precopact expansion $\mathbb{K}^\star$ that is Fraïssé and has the (EP) and the (RP).
Every element in $\text{Age}(\mathbb{K})$ has a finite Ramsey degree.

Definition. A structure $A \in \text{Age}(\mathbb{K})$ has finite Ramsey degree (in $\mathbb{K}$ if there is a $t_A \in \mathbb{N}$ such that $\forall k \in \mathbb{N}, \forall B \in \text{Age}(\mathbb{K})$ there is a $C \in \text{Age}(\mathbb{K})$ such that
$\displaystyle C \longrightarrow (B)_{k, t_A}^A.$
That is, there is a $\tilde{B}$ such that $\leq t_A$ colours appear on $\binom{\tilde{B}}{A}$ .

One way to interpret this result is that if you have a combinatorial property (3), then you get a precompact expansion with the (EP) and the (RP). This suggests (or at least seems to suggest) that precompact expansions are the relevant ones to consider.

Precompact questions

Natural question (Tsankov 2009). Which $\mathbb{K}$ satisfy these theorems? (Just knowing $\mathbb{K}$ and not assuming (RP).)

Conjecture (Nguyen Van Thé 2012). When $\mathbb{K}$ is precomapct.

This conjecture was shown to be false in 2015 by Evans using a Hrushovski construction. See his DocCourse lectures.

Conjecture (Bodirsky, Pinsker). This should be true for finite languages.

“What does the finite language mean topologically? Something about growth rate of number of structures of cardinality $n$ ? Related to amenability? Maybe the arity matters? This might require more examples of high arity.”

Openings from KPT

Research has gone in many directions from the original KPT paper.

Continuous versions, metric Fraïssé. (See Dana Bartosova’s lectures later in the DocCourse.) This is useful to prove that some Polish groups are extremely amenable. e.g. the automorphism group of the Gurarij space, the homeomorphisms of the Poulsen space.
KPT for other classes of things; i.e. universal minimal flow adjusted for distal or proximal flows. Melleray-Nguyen Van Thé-Tsankov 2016
There are still some particular Ramsey problems for specific classes (still open after 10 years!) Euclidean metric spaces, and equidistributed Boolean algebras.
Measures on $M(\text{Aut}(\mathbb{K}))$ . Which ones? How many? Angel-Kechris-Lyons 2014, Pawliuk-Sokic 2015.

References

Main references:

Kechris, Pestov, Todorcevic. “Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups”. 2005.
Pestov. “Dynamics of infinite-dimensional groups. The Ramsey-Dvoretzky-Milman phenomenon.”. 2006.
Ngyuen Van Thé. “More on the Kechris–Pestov–Todorcevic correspondence: Precompact expansions”. 2013
Ngyuen Van Thé. “A survey on structural Ramsey theory and topological dynamics with the Kechris-Pestov-Todorcevic correspondence in mind”. 2015

Other works cited (Mike: I have to fix some of these. This is obviously unfinished.)

Dana – Guraji
Dana – Poulsen
Angel, Kechris, Lyons. “Random Orderings and Unique Ergodicity of Automorphism Groups.” 2014
Pawliuk, Sokic. “Amenability and unique ergodicity of automorphism groups of countable homogeneous directed graphs.” [LINK] 2016
Zucker. “Topological dynamics of automorphism groups, ultrafilter combinatorics, and the generic point problem.” 2016.
Melleray, Nguyen Van Thé, Tsankov. “Polish groups with metrizable universal minimal flows.” 2016.
Evans – Hrushovski