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, -very-sparse iff -orientable, Existence of graph without Ramsey expansion.

**Definitions:** -very-sparse, -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 -categorical structure with no precompact Ramsey expansion.

Note that this will not be homogeneous for a *finite* relational language.

**Open question**. Suppose that is a countable structure, homogeneous for a fintie relational language. Does have a precompact Ramsey expansion?

It is not clear why a finite language should be better behaved than -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 be a relational first order language. An -structure is

**homogeneous**(or ultrahomogeneous) if isomorphisms of finite substructures of extend to automorphisms of .

Homogeneity is studied in Bootcamp 5.

**Definition**. Let . An structure is a

**reduct**(or shadow) of an structure if . Conversely, such an is an

**expansion**(or lift) of an structure .

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

**Fact**. If is an expansion of , then they have the same domain and . 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 has an expansion such that , and is homogeneous.

The idea is to expand the language to which distinguishes the different orbits. Add an -ary relation for each orbit on .

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

**Example**. Let , where is the succesor relation (true only if ). Note that this is not -categorical (or -homogeneous) because there are infinitely many types of pairs. Concretely, there are the formulas where is “” and is ““, etc..

By adding the relations () into the language we get a homogeneous structure in the language . In effect, we made the structure -homogeneous by distinguishing the different orbits of pairs.

**Definition**. If is an -structure, then is the class of isomorphism types of finite substructures.

**Theorem (Fraïssé)**. If is countable and homogeneous, then has the amalgamation property. Moreover it is a Fraïssé class and the Fraïssé limit of is .

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

**Definition**. Say that a countable homogeneous structure is a

**Ramsey structure**if 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 is a Ramsey class (with the

**JEP**) then has \textbf{AP}. So there is a countable homogeneous structure with .

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 is an expansion of , so that .

We say that is a **precompact expansion** of if , each orbit on is a union of finitely many orbits.

**Remark**. If and are both homogeneous, is a precompact expansion, then each expands to only finitely many structures in . 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 -categorical structure means that has finitely many orbits on for all . See Michael Pinkser’s lectures for more discussion.

So in order to prove our main theorem, we will construct a graph where:

- has only finitely many orbits on , but
- Every Ramsey expansion will have infinitely many orbits for pairs.

## Very sparse graphs

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 where (the unordered pairs of ). is for relation.

If , then , so (B, R^B) is the induced graphs from . We will often (lazily) denote this by .

### 4.2 -very-sparse graphs

**-very-sparse**if finite we have

An infinite graph is very sparse if it is -very-sparse for some .

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 (which is not so interesting) then is -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 is a graph (with possible other relations) is a very-sparse graph where all vertices have infinite degree. If is a Ramsey expansion of then has infinitely many orbits on . In particular, if has finitely many orbits on , then has no precompact Ramsey expansions.

### 4.4 The Hrushovski graph

**Theorem (Hrushovski 1988)**. There is an -categorical graph 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, -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 . A graph is **-orientable** if there is an orientation of the edges where each vertex has out-degree .

More technically, there is a digraph with out-degree , and , we have iff or .

Call a **-orientation of **.

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

This exercise hints at a more general fact.

**Theorem (Known to graph theorists)**. A graph is -orientable iff it is -very-sparse.

**Proof**. The direction is easy, so we focus on the 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 be a finite bipartite graph. For a set of vertices in , let denote the neighborhood of in , i.e. the set of all vertices in adjacent to some element of . There is a matching that entirely covers if and only if for every subset of :

Assume that is -very-sparse. We construct a bipartite graph where . The edge relation is given by and for all .

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

Let be a set of edges. Let be its vertices.

By sparseness . Since is all induced edges on , but is only some of them, we get . Thus

By the marriage theorem there is a complete matching of into . To get an orientation of , if is in the matching (for some ), then orient as .

**Exercise**. Show that this is a -orientation of .

### Orientability and sparseness

**Corollary**. is -very-sparse iff there is an edge partition such that each is -very-sparse.

The second condition is equivalent to saying that is the union of many -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 be a -very-sparse graph, and let be a Ramsey expansion of . We want to show that has infinitely many orbits on .

**Step 1**. There is an -invariant -orientation of .

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 all -orientations of is a closed (so compact) non-empty (by assumption) space. It is clear that acts on it, so it is a flow. Since this expansion is Ramsey, must have a fixed point. This fixed point will be the desired invariant -orientation.

Now we give a proof without KPT. Suppose that is a an -orbit (thought of as ordered pairs).

Since is Ramsey (and hence rigid), if then .

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

- , or
- .

**Claim**. If are distinct orbits, then there are such that the set of directed edges

gives a digraph which has out-degree .

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 such that for every vector there is a finite substructure of that witnesses the fact that the digraph has out-degree . Since such a witness is finite, we may assume there is a finite that contains each and only has edges of types .

Let be an edge of type which is a structure in . Since is a Ramsey class, we can stabilize each edge type for two colours. More precisely:

- There is a such that .
- There is a such that .
- There is a such that .

Now we use a Sierpinski colouring trick.

Let be an arbitrary -orientation of . We will find a copy of in which will be a contradiction. To do this we use Ramsey to restrict to a copy of where the direction of the edges in depend only on the orbits .

Define a -colouring of by iff . That is, the directed edge in agrees with the order of in the orbit it comes from.

So by Ramsey, there is a such that is constant, and equal to on each . Now is a digraph of the form .

However, has a vertex with out-degree , contradicting the fact that is a -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 -orientation ; those edges are fixed for the rest of the proof. All we do is use Ramsey to find a copy of where the direction of the edges in depend only on the orbits . We know if that happens then it is of the form .

## 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.

## One thought on “Hrushovski constructions – Ramsey DocCourse Prague 2016”