The following notes are from the Ramsey DocCourse in Prague 2016. The notes were taken and edited by myself and Michael Kompatscher. In the process we may have included some errors; email us or comment below and we will happily fix them.

**Title**: Bootcamp 2 (of 8)

**Lecturer**: Jaroslav Nešetřil.

**Date**: September 21, 2016.

**Main Topics**: The Rado graph, homogeneous structures, universal graphs

**Definitions:** Language, structures, homomorphisms, embeddings, homogeneity, universality, Rado graph (Random graph),…

Bootcamp 1 – Bootcamp 2 – Bootcamp 3 – Bootcamp 4 – Bootcamp 5 – Bootcamp 6 – Bootcamp 7 – Bootcamp 8

## Introduction

In this lecture we discussed some standard notions from model theory that will be used in the rest of the Bootcamp lectures. Further we discussed the Rado graph (also known as Random graph) as an example of a homogeneous structure.

## Structures

**Definition**. A language (or signature) is a set of symbols, which can be diveded into relational symbols (usually denoted by capital letters ) and functional symbols (usually described by lowercase letters ). To every symbol we associate an natural number , the arity of .

Then an **-structure ** is a triple , where is called the domain of and the interpretation function. For we require that for every relational symbol (i.e. is an -ary relation on ) and is a function from A$.

For simplicity, we usually don’t talk about the interpretation function and write and . If it is clear from the context, we sometimes abuse notation and write for both the symbol and its interpretation in a structure.

Constants can be regarded as unary singleton relations, or as 0-ary functions. However, in the Bootcamp lectures, we are only going to discuss relational structures, i.e. structures whose language only consists of relational symbols.

**Definition**. Let and be two -structures on domain , respectively . Then a map is called an (-)homomorphism, if, for every relation symbol :

and for every function symbol :

A function is called a strong homomorphism if futher .

Injective homomorphisms are called monomorphisms, injective strong homomorphisms are called embeddings, bijective embeddings are called isomorphisms. An isomorphism from a structure to itself is called an automorphism of .

We say is a substructure , if and the identity is an embedding of into . If there is an embedding of , we call the image a copy of in .

## The Rado graph

Erdös and Rényi showed the paradoxical result that there is a unique (and highly symmetric) countably infinite random graph. We are going to discuss this graph and some of its properties in this section.

**Definition**. Let us say a countable graph satisfies the

**extension property**, if for all finite, disjoint subsets there is a point such that has an edge with every element of and no edge with elements from .

**Lemma**. If and are two countable graphs with the extension property, then and are isomorphic.

**Proof.**We are going to construct an isomorphism from to as the union of a sequence of isomorphisms between finite substructures of and that extend each other. Let us fix an enumeration of the vertices and an enumeration of the elements of .

Suppose we have already constructed an isomorphism from a finite subset to . Then let be the first element of ; it gives us a partition of into the set of its neighbors and non-neighbors . By the extension property of , there is also a vertex in such that has an edge with all elements of and has no edge with elements of . By setting we extended the given isomorphism to .

To ensure that every vertex of is in the image of we alternate in the next step, finding a suitable preimage of the first element of . This can be done symmetrically by the extension property of .

Since both graphs and are countable, the union of this ascending sequence of finite isomorphisms is an isomorphism from to .

The technique used in proof above is known as **back-and-forth argument** or **zig-zag argument**. This proof techniques appears also in other talks of the course, in particular in the proof of Fraïssé’s theorem in Bootcamp 5.

It is not difficult to show that there are graphs with the extension property. An explicit description of such a graph was given by Rado in 1964. The vertex set of the Rado graph are the natural numbers, where for there is an edge between and if and only if the binary representation of has a on its -th position.

**Exercise**. Show that the Rado graph satisfies the extension property for graphs.

There is also a probabilistic characterization of such graphs by Erdös and Rényi, which preceded Rado’s construction. Let us denote by a random graph a probabilistic distribution over graphs, in which the probabilities for edges are distributed independently, with probability each (Note by Michael: In literature the term “random graph” sometimes also refers to graphs generated by some other random process).

Then the following holds:

**Theorem (Erdös, Rényi, 1963)**. A countable random graph is isomorphic to the Rado graph with probability 1.

**Proof**. If we are able to show that the random graph satisfies the extension property with probability 1, we are done. So let and be two finite, disjoint sets of vertices in and let . Then, for any vertex the probability that there has edges to the elements of and only non-edges with the elements of is equal to . Since edges and non-edges are distributed independently, the probability that there is no such vertex is equal to .

By the above theorem the Rado graph is often also called the Random graph. The Rado graph has several other nice features, making it a highly symmetric structure:

- For two finite, disjoint subsets of there are always infinitely many points witnessing the extension property (with respect to and ).
- Therefore removing finitely many points of results in an graph that is isomorphic to .
- The same holds for removing/adding finitely many edges.
- If we change all edges of to non-edges and vice-versa, the resulting graph is isomorphic to .
- The same holds for switching edges and non-edges between a finite set and its complement.
- is universal, in the sense that it embeds all countable graphs.

## Homogeneous structures

**Definition**. Let be a structure in relational language. Then we say that is

**homogeneous**if every isomorphism between finite substructures of extends to an automorphism of .

Examples:

- the rational order is homogeneous: It can be easily seen that every isomorphism between finite substructures can be extended by a piecewise linear map to an automorphism of
- The Rado graph is homogeneous. This can be shown by a back-and-forth argument as in the proof that the Rado graph is isomorphic to every other graph with the extension property.
- The Peterson graph is an example of a graph with many symmetries, in particular its automorphism group is transitive (i.e. for every two elements there is an automorphism mapping to ). However the Petersen graph is not homogeneous: In the image below, the induced subgraphs given by the blue points and te green points are isomorphic, but there is not automorphism extending this map, since the blue points have a common neighbor, but the green points not.

In the case of graphs a full classification of the homogeneous graphs is known: in the finite case this classification is due to Gardiner, in the countable case due to Lachlan and Woodrow.

**Theorem (Gardiner 1976)**Whenever is a finite, homogeneous graph it is isomorphic to one of the following:

- The disjoint union of finitely many cliques of the same size
- the 5-cycle
- the 3-cycle
- the 3×3 rook’s graph , shown in the picture below

**Theorem (Lachlan, Woodrow 1980)**. Whenever is a countable, homogeneous graph it is isomorphic to one of the following:

- The disjoint union of copies of , where at least one of the numbers is
- the Rado graph
- a universal, -free homogeneous graph for (also known as Henson graph )
- a complements of the above.

We will hear more about homogeneous structures and a way of constructing them in Bootcamp 5.

## Universal graphs

**Definition**. Let be a class of structures in the same language. The we say that is (-)universal, if every element of embeds into .

Examples:

- the Rado graph is universal with respect to the class of countable graphs.
- The Henson graph is universal with respect to the class of countable -free graphs.
- The rational order is universal with respect to the class of countable linear orders.

In this section we are going to show that not for every class of countable structure there is a -universal structure. A counterexample for graphs was given by Füredi and Komjáth:

**Theorem (Füredi, Komjáth 1997)**. There is no countable graph , such that is universal for the class of -free graphs, i.e. the class of graphs that do not contain as a subgraph.

We remark that this result was proven in a more general setting (substitute by any finite, 2-connected, but not complete graph); but here we only present a proof for .

**Proof sketch**. We are going to use the following lemma:

**Lemma**. For all integers there exists a number and an -regular hypergraph on vertex set and edges set , such that

- the girth of is at least (in particular if )
- (i + N) \in E_i \subseteq \{i-N, i-N+1, \ldots, i+N\}
- The rational order is universal with respect to the class of countable linear orders.

(Michael: My notes on the proof of this lemma are not complete…)

Now let us take the hypergraph given by the above Lemma. Further let , be graphs on 7-element vertex set, such that in the first 4 elements form a path and the last 3 a cycle; and in also the last 3 elements form a cycle and there is an edge from the first to the forth vertex.

For every function we then form a -free graph on , by replacing every hyperedge in by if and by if . Note that the graph is well-defined and -free by the properties of .

Now assume that there is a countable universal -free graph . Then has to embed all the graphs of the form ; For every let be an embedding of into . Since is countable, there are two graphs , , such that and agree on the set . But since , there has to be a minimal integer , where they disagree. Then, by construction of the graphs and , the union has to contain a 4-cycle. But this is a contradiction.

## References

- Peter Cameron, The Random graph, 2013.
- Dugald MacPherson, A survey of homogeneous structures, 2011.

## One thought on “Bootcamp 2 – Ramsey DocCourse Prague 2016”