Hrushovski constructions – 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: Hrushovski constructions 1 (of 3)

Lecturer: David Evans

Date: November 7, 2016

Main Topics: Definition Review, $k$ -very-sparse iff $k$ -orientable, Existence of graph without Ramsey expansion.

Definitions: $k$ -very-sparse, $k$ -orientable,

1. Introduction

Our main goal is to give an interesting graph that doesn’t admit a precompact Ramsey expansion. This answers a question that has been open since 2010 (which we talk about in Bootcamp 7 and Michael Pinsker’s lecture 3).

Our plan is as follows:

Provide some historical context.
Explain the terminology.
State the properties that the graph must have.
Prove the theorem assuming such a graph exists.

In the next lecture we will show how to construct such a graph. It will be a generalization of the Fraïssé construction.

The original parts of these lectures are joint work with Hubička and Nešetřil.

2. Historical context

This section will be a bit vague and will lack definitions. It is mostly meant to impart a rough timeline and how these objects are not pathological; they appear in other parts of mathematics.

Hrushovki-type amalgamation constructions (or predimension constructions) first appeared in preprints in 1988. Some of the ones we are going to discuss never even made it to print.

These provided counterexamples to some appealing conjectures. They showed that “The world is a little more complicated than you might have thought… but in an interesting way.”

These constructions are related to cotransversal matroids, and also Shelah-Spencer, Baldwin-Shelah work about sparse random graphs. “These constructions show up in other parts of mathematics.”

We’ll focus on the applications to structural Ramsey theory. Specifically we will work towards proving the following new result.

Theorem (E 2016). There is a countable $\omega$ -categorical structure $\mathcal{M}$ with no precompact Ramsey expansion.

Note that this $\mathcal{M}$ will not be homogeneous for a finite relational language.

Open question. Suppose that $\mathcal{N}$ is a countable structure, homogeneous for a fintie relational language. Does $\mathcal{N}$ have a precompact Ramsey expansion?

It is not clear why a finite language should be better behaved than $\omega$ -categorical in this setting.

3. Terminology and notation; What the words mean.

3.1 Basic definition review

We review some basic definitions that have been introduced in previous lectures.

Definition. Let $L$ be a relational first order language. An $L$ -structure $\mathcal{N}$ is homogeneous (or ultrahomogeneous) if isomorphisms of finite substructures of $\mathcal{N}$ extend to automorphisms of $\mathcal{N}$ .

Homogeneity is studied in Bootcamp 5.

Definition. Let $L \subset L^+$ . An $L^+$ structure $\mathcal{N}^+$ is a reduct (or shadow) of an $L$ structure $\mathcal{N}$ if $\mathcal{N}^+ \vert L = \mathcal{N}$ . Conversely, such an $\mathcal{N}^+$ is an expansion (or lift) of an $L$ structure $\mathcal{N}$ .

Expansions are studied in Bootcamp 5 (Introduction and motivation), Bootcamp 7 (Examples and history) and Bootcamp 8 (more examples and classifications).

Fact. If $\mathcal{N}^+$ is an expansion of $\mathcal{N}$ , then they have the same domain and $\text{Aut}(\mathcal{N}^+) \leq \text{Aut}(\mathcal{N})$ . Moreover, this is a closed subgroup if the automorphism group is given the pointwise convergence topology.

We go into more detail about the pointwise convergence topology in Michael Pinsker’s Lecture 1.

Fact. Every structure $\mathcal{N}$ has an expansion $\mathcal{N}^+$ such that $\text{Aut}(\mathcal{N}^+) = \text{Aut}(\mathcal{N})$ , and $\mathcal{N}^+$ is homogeneous.

The idea is to expand the language to $L^+$ which distinguishes the different orbits. Add an $n$ -ary relation for each $\text{Aut}(\mathcal{N})$ orbit on $N^n$ .

To a model theorist, this is saying you can assume some amount of quantifier elimination, as we see in the next example.

Example. Let $\mathcal{N} = (\mathbb{N}, s(x,y))$ , where $s(x,y)$ is the succesor relation (true only if $y = x+1$ ). Note that this is not $\omega$ -categorical (or $2$ -homogeneous) because there are infinitely many types of pairs. Concretely, there are the formulas $\phi_n(x,y)$ where $\phi_2(x,y)$ is “ $\exists a (s(x,a) \wedge s(a,y))$ ” and $\phi_3(x,y)$ is “ $\exists a, \exists b (s(x,a) \wedge s(a,b) \wedge s(b,y))$ “, etc..

By adding the relations $\phi_n$ ( $\forall n$ ) into the language we get $\mathcal{N}^+$ a homogeneous structure in the language $\{s(x,y)\} \cup \{\phi_n(x,y) : n \in \mathbb{N}\}$ . In effect, we made the structure $2$ -homogeneous by distinguishing the different orbits of pairs.

Definition. If $\mathcal{M}$ is an $L$ -structure, then $\text{Age}(\mathcal{M})$ is the class of isomorphism types of finite substructures.

Theorem (Fraïssé). If $\mathcal{M}$ is countable and homogeneous, then $\text{Age}(\mathcal{M})$ has the amalgamation property. Moreover it is a Fraïssé class and the Fraïssé limit of $\text{Age}(\mathcal{M})$ is $\mathcal{M}$ .

We go into more detail about the Fraïssé correspondence in Bootcamp 5.

Definition. Say that a countable homogeneous structure $\mathcal{M}$ is a Ramsey structure if $\text{Age}(\mathcal{M})$ is a Ramsey class (when colouring embeddings).

If in addition we assume that the structure has a linear order (or more generally is rigid) then embedding-Ramsey is the same as Ramsey when colouring substructures.

It makes sense to talk about Ramsey for structures and not just Ramsey for classes.

Theorem (Nešetřil). If $\mathcal{C}$ is a Ramsey class (with the JEP) then $\mathcal{C}$ has \textbf{AP}. So there is a countable homogeneous structure $\mathcal{M}$ with $\mathcal{C} = \text{Age}(\mathcal{M})$ .

We saw a proof for this in Bootcamp 4 (using hypergraphs) and Bootcamp 5 (directly).

3.2 Precompactness

We now introduce one of the important properties of expansions.

Definition. Suppose that $\mathcal{N}^+$ is an expansion of $\mathcal{N}$ , so that $\text{Aut}(\mathcal{N}^+) \leq \text{Aut}(\mathcal{N})$ .

We say that $\mathcal{N}^+$ is a precompact expansion of $\mathcal{N}$ if $\forall n \in \mathbb{N}$ , each $\text{Aut}(\mathcal{N})$ orbit on $N^n$ is a union of finitely many $\text{Aut}(\mathcal{N}^+)$ orbits.

Remark. If $\mathcal{N}$ and $\mathcal{N}^+$ are both homogeneous, $\mathcal{N}^+$ is a precompact expansion, then each $A \in \text{Age}(\mathcal{N})$ expands to only finitely many structures in $\mathcal{N}^+$ . This also says that the reduct map is finite-to-one.

The name makes more sense in the KPT setting. This will be explained more in Lionel’s talks next week.

3.3 The plan of attack

Using the Ryll-Nardzewski theorem, a countable $\omega$ -categorical structure $\mathcal{M}$ means that $\text{Age}(\mathcal{M})$ has finitely many orbits on $M^n$ for all $n \in \mathbb{N}$ . See Michael Pinkser’s lectures for more discussion.

So in order to prove our main theorem, we will construct a graph $\mathcal{M}$ where:

$\text{Aut}(\mathcal{M})$ has only finitely many orbits on $M^2$ , but
Every Ramsey expansion $\mathcal{M}^+$ will have infinitely many $\text{Aut}(\mathcal{M}^+)$ orbits for pairs.

Very sparse graphs

As pointed out by Andrés, both “sparsity” and “sparseness” are acceptable ways to describe “the state of being sparse”.

The structure we will construct will be a graph, so we introduce some notation and facts about graphs.

4.1 Notation

We will represent a graph by $\Gamma = (A, R)$ where $R \subseteq [A]^2$ (the unordered pairs of $A$ ). $R$ is for relation.

If $B \subseteq A$ , then $R^B = [B]^2 \cap R$ , so (B, R^B) is the induced graphs from $B$ . We will often (lazily) denote this by $B$ .

4.2 $k$ -very-sparse graphs

Let $k \in \mathbb{N}$ . A graph $\Gamma = (A,R)$ is $k$ -very-sparse if $\forall$ finite $B \subseteq A$ we have

$\displaystyle \vert R^B \vert \leq k\vert B \vert.$
An infinite graph is very sparse if it is $k$ -very-sparse for some $k$ .

See Nešetřil’s article for a discussion of “What is the right definition of sparse?”. [Mike’s comment I’m missing this reference. Anyone know what it is?]

Exercise. For $k=1$ (which is not so interesting) then $\Gamma$ is $1$ -very-sparse iff it is a cycle, a tree or a single cycle with trees attached to it.

4.3 The main theorem

Here is the main theorem we will show.

Theorem (E 2016). Suppose that $\mathcal{M} = (M, R, \ldots)$ is a graph (with possible other relations) is a very-sparse graph where all vertices have infinite degree. If $\mathbb{M}^+$ is a Ramsey expansion of $\mathbb{M}$ then $\text{Aut}(\mathbb{M}^+)$ has infinitely many orbits on $M^2$ . In particular, if $\text{Aut}(\mathbb{M})$ has finitely many orbits on $M^2$ , then $\mathbb{M}$ has no precompact Ramsey expansions.

4.4 The Hrushovski graph

Theorem (Hrushovski 1988). There is an $\omega$ -categorical graph $\mathcal{M}$ satisfying the hypothesis of the main theorem.

Sparseness is a key feature of Hrushovski’s construction. It’s what it’s all about. It’s not ad hoc.

Any such example of a sparse, $\omega$ -categorical graph would be a counterexample to Lauchlan’s conjecture. (We will not get into that here. It’s just meant to point out that such graphs are interesting.)

4.5 Orientability

Definition. Let $k \in \mathbb{N}$ . A graph $\Gamma = (A,R)$ is $k$ -orientable if there is an orientation of the edges where each vertex has out-degree $\leq k$ .

More technically, there is a digraph $D = (A,S)$ with out-degree $\leq k$ , and $\forall a,b \in A$ , we have $\{a,b\}\in R$ iff $(a,b)\in S$ or $(b,a)\in S$ .

Call $D$ a $k$ -orientation of $\Gamma$ .

Exercise. Using the previous exercise, show that every $1$ -very-sparse graph is $1$ -orientable.

This exercise hints at a more general fact.

Theorem (Known to graph theorists). A graph $\Gamma$ is $k$ -orientable iff it is $k$ -very-sparse.

Proof. The $\Rightarrow$ direction is easy, so we focus on the $\Leftarrow$ direction.

Note that a straightforward compactness argument shows that it suffices to show this for finite graphs. (See the last proof in Boootcamp 5 for an example of such an argument.)

We set up a use of Hall’s marriage theorem.

Hall’s marriage theorem. Let $G = (V_1 \cup V_2, E)$ be a finite bipartite graph. For a set $I$ of vertices in $V_1$ , let $N_G (I)$ denote the neighborhood of $I$ in $G$ , i.e. the set of all vertices in $V_2$ adjacent to some element of $I$ . There is a matching that entirely covers $V_1$ if and only if for every subset $I$ of $V_1$ :

$\displaystyle |I|\leq |N_{G}(I)|.$

Assume that $\Gamma = (A,R)$ is $k$ -very-sparse. We construct a bipartite graph $G = (V, E)$ where $V = R\cup A\times[k]$ . The edge relation is given by $\{a,b\} E (a,l)$ and $\{a,b\} E (b,l)$ for all $l \leq k$ .

We check that Hall’s marriage theorem applies by checking the degree estimate.

Let $I \subseteq R$ be a set of edges. Let $C = \cup I \subseteq A$ be its vertices.

By sparseness $k \vert C \vert \geq \vert R^C \vert$ . Since $R^C$ is all induced edges on $C$ , but $I$ is only some of them, we get $\vert R^C \vert \geq \vert I \vert$ . Thus

$\displaystyle k \vert C \vert \geq \vert R^C \vert \geq \vert I \vert.$

By the marriage theorem there is a complete matching of $R$ into $A \times [k]$ . To get an orientation of $\Gamma$ , if $(\{a,b\}, (a,l))$ is in the matching (for some $l \leq k$ ), then orient $\{a,b\}$ as $a \rightarrow b$ .

Exercise. Show that this is a $k$ -orientation of $\Gamma$ .

Orientability and sparseness

Corollary. $\Gamma = (A,R)$ is $k$ -very-sparse iff there is an edge partition $\chi:R \rightarrow [k]$ such that each $(A, \chi^{-1}(i))$ is $1$ -very-sparse.

The second condition is equivalent to saying that $\Gamma$ is the union of $k$ many $1$ -very-sparse weak subgraphs.

5. The proof of the main theorem

We are finished the preliminaries and can begin the proof of the theorem.

Proof of main theorem. Let $\mathcal{M} = (M,R)$ be a $k$ -very-sparse graph, and let $\mathcal{N}$ be a Ramsey expansion of $\mathcal{M}$ . We want to show that $\text{Aut}(\mathcal{N})$ has infinitely many orbits on $M^2$ .

Step 1. There is an $\text{Aut}(\mathcal{N})$ -invariant $k$ -orientation of $(M,R)$ .

We will complete a proof of this step today, and leave the rest of the steps in the proof for the next lecture. We give two proofs of this fact. These proofs mirror the proof that appears at the end of Bootcamp 5.

Proof using KPT correspondence. First we give a KPT proof, which is quick but requires the KPT technology. The collection $X = \{$ all $k$ -orientations of $(M,R) \} \subset 2^{M^2}$ is a closed (so compact) non-empty (by assumption) space. It is clear that $\text{Aut}(\mathcal{N})$ acts on it, so it is a flow. Since this expansion is Ramsey, $X$ must have a fixed point. This fixed point will be the desired invariant $k$ -orientation.

Now we give a proof without KPT. Suppose that $\Delta \subseteq R \subseteq M^2$ is a an $\text{Aut}(\mathcal{N})$ -orbit (thought of as ordered pairs).

Since $\mathcal{N}$ is Ramsey (and hence rigid), if $(a,b) \in \Delta$ then $(b,a) \notin \Delta$ .

Now we need to choose an orientation for every $\Delta$ . There are two choices:

$\Delta^0 := \Delta$ , or
$\Delta^1 := \{(b,a) : (a,b) \in \Delta\}$ .

Claim. If $\Delta_1, \ldots, \Delta_r$ are distinct orbits, then there are $\epsilon_1, \ldots, \epsilon_r \in \{0,1\}$ such that the set of directed edges

$\displaystyle R_{\epsilon_1, \ldots, \epsilon_r} := \Delta_1^{\epsilon_1} \cup \ldots \cup \Delta_r^{\epsilon_r}$
gives a digraph $(M, R_{\epsilon_1, \ldots, \epsilon_r})$ which has out-degree $\leq k$ .

Once we have this claim, then Step 1 will follow by a compactness argument.

Proof of claim. Suppose the claim is false. Then there is an $r$ such that for every vector $\overline{\epsilon}$ there is a finite substructure $B_\overline{\epsilon}$ of $\mathcal{N}$ that witnesses the fact that the digraph $(M, R_\overline{\epsilon})$ has out-degree $\geq k$ . Since such a witness is finite, we may assume there is a finite $B$ that contains each $B_\overline{\epsilon}$ and only has edges of types $\Delta_1, \ldots, \Delta_r$ .

Let $E_i$ be an edge of type $\Delta_i$ which is a structure in $\mathcal{N}$ . Since $\mathcal{N}$ is a Ramsey class, we can stabilize each edge type $E_i$ for two colours. More precisely:

There is a $C_1 \in \text{Age}(\mathcal{N})$ such that $C_1 \Rightarrow (B)_2^{E_1}$ .
There is a $C_2 \in \text{Age}(\mathcal{N})$ such that $C_2 \Rightarrow (C_1)_2^{E_2}$ .
$\ldots$
There is a $C = C_r \in \text{Age}(\mathcal{N})$ such that $C_r \Rightarrow (C_{r-1})_2^{E_{r-1}}$ .

Now we use a Sierpinski colouring trick.

Let $(M,D)$ be an arbitrary $k$ -orientation of $(M,R)$ . We will find a copy of $(B, R_{\overline{\epsilon}})$ in $(M,D)$ which will be a contradiction. To do this we use Ramsey to restrict to a copy of $B$ where the direction of the edges in $D_B$ depend only on the orbits $\Delta_i$ .

Define a $2$ -colouring $\rho$ of $(\Delta_1 \cup \ldots \cup \Delta_r) \cap C^2$ by $\rho((a,b)) = 0$ iff $(a,b) \in D$ . That is, the directed edge in $D$ agrees with the order of $(a,b)$ in the orbit $\Delta_i$ it comes from.

So by Ramsey, there is a $B_1 \in \binom{C}{B}$ such that $\rho$ is constant, and equal to $\eta_i$ on each $\Delta_i$ . Now $(B_1, D_{B_1}) \leq (M, D)$ is a digraph of the form $(B_1, R_{\overline{\eta}})$ .

However, $(B_1, R_{\overline{\eta}})$ has a vertex with out-degree $\geq k+1$ , contradicting the fact that $(M, D)$ is a $k$ -orientation.

Mike’s comment. The proof of this claim took me about 4 hours to understand. The key insight to understanding it is that you never change the direction of the arbitrary $k$ -orientation $(M,D)$ ; those edges are fixed for the rest of the proof. All we do is use Ramsey to find a copy of $B$ where the direction of the edges in $D_B$ depend only on the orbits $\Delta_i$ . We know if that happens then it is of the form $(B, R_{\overline{\eta}})$ .

References

Hrushovski (“Extending partial isomorphisms of graphs“, 1992) Hrushovski’s first published paper about this topic.
Milliet (“Extending partial isomorphisms of finite graphs [PDF]“, 2004) A short, very readable direct proof of Hrushovski for graphs.

Mike’s comment. I’m happy to include more references if you know them! Please comment below with the MathSciNet link.

2 thoughts on “Hrushovski constructions – Ramsey DocCourse Prague 2016”

Pingback: Functions on Homogeneous Ramsey Structures 3 – Ramsey DocCourse Prague 2016
Pingback: Unifying themes in Ramsey Theory – BIRS 2018 – Mike Pawliuk – Mathematics