Bootcamp 2 – Ramsey DocCourse Prague 2016 – Mike Pawliuk

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) $L$ is a set of symbols, which can be diveded into relational symbols (usually denoted by capital letters $R$ ) and functional symbols (usually described by lowercase letters $f$ ). To every symbol $R$ we associate an natural number $\text{ar}(R)$ , the arity of $R$ .

Then an $L$ -structure $\mathcal{A}$ is a triple $\mathcal{A} = (A,L,I)$ , where $A$ is called the domain of $\mathcal{A}$ and $I$ the interpretation function. For $I$ we require that $I(R): \subseteq A^{\text{ar}(R)}$ for every relational symbol $R$ (i.e. $I(R)$ is an $n$ -ary relation on $A$ ) and $I(f)$ is a function from $A^{\text{ar}(f)} to$ A$.

For simplicity, we usually don’t talk about the interpretation function and write $R^\mathcal{A} = I(R)$ and $f^\mathcal{A} = I(f)$ . If it is clear from the context, we sometimes abuse notation and write $R$ 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 $\mathcal A$ and $\mathcal B$ be two $L$ -structures on domain $A$ , respectively $B$ . Then a map $f: A \to B$ is called an ( $L$ -)homomorphism, if, for every relation symbol $R \in L$ :
$\displaystyle (a_1,\ldots,a_n) \in R^{\mathcal A} \Rightarrow (f(a_1),\ldots,f(a_n)) \in R^{\mathcal A}$
and for every function symbol $g \in L$ :
$\displaystyle f(g^{\mathcal A}(a_1,\ldots,a_n)) = g^{\mathcal B}(f(a_1),\ldots,f(a_n)).$
A function $f: A \to B$ is called a strong homomorphism if futher $(a_1,\ldots,a_n) \in R^{\mathcal A} \Leftrightarrow (f(a_1),\ldots,f(a_n)) \in R^{\mathcal A}$ .

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

We say $\mathcal A$ is a substructure $\mathcal B$ , if $A \subseteq B$ and the identity is an embedding of $\mathcal A$ into $\mathcal B$ . If there is an embedding of $e: \mathcal A \to \mathcal B$ , we call the image $e(\mathcal A)$ a copy of $\mathcal A$ in $\mathcal B$ .

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 $(V,E)$ satisfies the extension property, if for all finite, disjoint subsets $A,B \subseteq V$ there is a point $x \in V$ such that $x$ has an edge with every element of $A$ and no edge with elements from $B$ .

Lemma. If $G$ and $G'$ are two countable graphs with the extension property, then $G$ and $G'$ are isomorphic.

Proof. We are going to construct an isomorphism from $G = (V,E)$ to $G' = (V,E')$ as the union of a sequence of isomorphisms between finite substructures of $G$ and $G'$ that extend each other. Let us fix an enumeration of the vertices $V$ and an enumeration of the elements of $V'$ .

Suppose we have already constructed an isomorphism $I$ from a finite subset $A \subseteq V$ to $I(A) \subseteq V'$ . Then let $a$ be the first element of $V \setminus A$ ; it gives us a partition of $A$ into the set of its neighbors $A_E = \{x \in A: E(x,a)\}$ and non-neighbors $A_{\bot} = \{x \in A: \not E(x,a)\}$ . By the extension property of $G'$ , there is also a vertex $a'$ in $V'$ such that $a'$ has an edge with all elements of $I(A_E)$ and has no edge with elements of $I(A_{\bot})$ . By setting $I(a) = a'$ we extended the given isomorphism to $A \cup \{a\}$ .

To ensure that every vertex of $G'$ is in the image of $I$ we alternate in the next step, finding a suitable preimage of the first element of $G' \setminus I(A)$ . This can be done symmetrically by the extension property of $G$ .

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

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 $\mathcal R$ are the natural numbers, where for $a < b$ there is an edge between $a$ and $b$ if and only if the binary representation of $B$ has a $1$ on its $a$ -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 $\frac{1}{2}$ 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 $X$ is isomorphic to the Rado graph $\mathcal R$ with probability 1.

Proof. If we are able to show that the random graph $X$ satisfies the extension property with probability 1, we are done. So let $A$ and $B$ be two finite, disjoint sets of vertices in $X$ and let $n = |A \cup B|$ . Then, for any vertex $x$ the probability that there $x$ has edges to the elements of $A$ and only non-edges with the elements of $B$ is equal to $2^{-n}$ . Since edges and non-edges are distributed independently, the probability that there is no such vertex is equal to $\prod_{x \in X\setminus (A \cup B) }(1-2^{-n}) = 0$ .

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

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

Homogeneous structures

Definition. Let $\mathcal A$ be a structure in relational language. Then we say that $\mathcal A$ is homogeneous if every isomorphism between finite substructures of $\mathcal A$ extends to an automorphism of $\mathcal A$ .

Examples:

the rational order $(\mathbb Q, <)$ 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 $(\mathbb Q, <)$
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 $a,b$ there is an automorphism mapping $a$ to $b$ ). 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 $G$ 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 $L(3,3)$ , shown in the picture below

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

The disjoint union of $m$ copies of $K_n$ , where at least one of the numbers $n,m$ is $\omega$
the Rado graph $\mathcal R$
a universal, $K_n$ -free homogeneous graph for $n \geq 3$ (also known as Henson graph $H_n$ )
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 $C$ be a class of structures in the same language. The we say that $\mathcal A \in C$ is ( $C$ -)universal, if every element of $C$ embeds into $\mathcal A$ .

Examples:

the Rado graph $\mathcal R$ is universal with respect to the class of countable graphs.
The Henson graph $H_n$ is universal with respect to the class of countable $K_n$ -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 $\mathcal C$ there is a $\mathcal C$ -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 $G$ , such that $G$ is universal for the class of $C_4$ -free graphs, i.e. the class of graphs that do not contain $C_4$ as a subgraph.

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

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

Lemma. For all integers $k,g$ there exists a number $N$ and an $k$ -regular hypergraph $H(k,g)$ on vertex set $\mathbb N$ and edges set $\{E_1,E_2,\ldots\}$ , such that

the girth of $H(k,g)$ is at least $g$ (in particular $|E_i\cap E_j| \leq 1$ if $g \geq 3$ )
(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 $H(7,5)$ given by the above Lemma. Further let $G_0$ , $G_1$ be graphs on 7-element vertex set, such that in $G_0$ the first 4 elements form a path and the last 3 a cycle; and in $G_1$ also the last 3 elements form a cycle and there is an edge from the first to the forth vertex.

For every function $f: \mathbb N \to \{0,1\}$ we then form a $C_4$ -free graph $G_f$ on $\omega$ , by replacing every hyperedge $E_i$ in $H(7,5)$ by $G_0$ if $f(i)=0$ and by $G_i$ if $f(i)=1$ . Note that the graph is well-defined and $C_4$ -free by the properties of $H(7,5)$ .

Now assume that there is a countable universal $C_4$ -free graph $U$ . Then $U$ has to embed all the graphs of the form $G_f$ ; For every $G_f$ let $e_f$ be an embedding of $G_f$ into $U$ . Since $U$ is countable, there are two graphs $G_{f}$ , $G_{h}$ , such that $e_f$ and $e_h$ agree on the set $\{1,2,\ldots,N\}$ . But since $f \neq h$ , there has to be a minimal integer $j+N$ , where they disagree. Then, by construction of the graphs $G_f$ and $G_h$ , the union $e_f(E_j) \cup e_h(E_j)$ has to contain a 4-cycle. But this is a contradiction.