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,
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.
Note that this will not be homogeneous for a finite relational language.
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.
Homogeneity is studied in Bootcamp 5.
Expansions are studied in Bootcamp 5 (Introduction and motivation), Bootcamp 7 (Examples and history) and Bootcamp 8 (more examples and classifications).
We go into more detail about the pointwise convergence topology in Michael Pinsker’s Lecture 1.
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.
We go into more detail about the Fraïssé correspondence in Bootcamp 5.
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.
We saw a proof for this in Bootcamp 4 (using hypergraphs) and Bootcamp 5 (directly).
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.
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
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?]
4.3 The main theorem
Here is the main theorem we will show.
4.4 The Hrushovski graph
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.)
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 .
This exercise hints at a more general fact.
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.
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 .
Orientability and sparseness
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.
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 .
- 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”