On pseudofiniteness and smoothly approximability

Question

Def1. (Ax1968) An $\Sigma$-structure $M$ is pseudofinite if for all $\Sigma$-sentences $\varphi$, $\mathcal{M}\models \varphi$ implies that there is a finite $\mathcal{M}_0$ such that $\mathcal{M}_0\models \varphi$. The theory $ T = Th (\mathcal{M}) $ of the pseudofinite structure $\mathcal{M}$ is called pseudofinite.

Def2. (Lachlan, Kantor,Liebeck,Macpherson) Let $\Sigma$ be a countable signature and let $\mathcal{M}$ be a countable and $\omega$-categorical $\Sigma$-structure. $\Sigma$-structure $\mathcal{M}$ (or $Th(\mathcal{M})$) is said to be smoothly approximable if there is an ascending chain of finite substructures $A_0 \subseteq A_1 \subseteq \ldots \subseteq \mathcal{M}$ such that $\bigcup_{i\in \omega} A_i = \mathcal{M}$ and for every $i$, and for every $\bar{a},\bar{b}\in A_i$ if $tp_{\mathcal{M}} (\bar{a}) = tp_{\mathcal{M}} (\bar{b})$, then there is an automorphism $\sigma$ of $M$ such that $\sigma(\bar{a}) =\bar{b}$ and $\sigma(A_i ) = A_i$, or equivalently, if it is the union of an $\omega$-chain of finite homogeneous substructures$^1$; or equivalently, if any sentence in $Th(\mathcal{M})$ is true of some finite homogeneous substructure of $\mathcal{M}$.

Why is the Rado graph (random graph) pseudofinite but not smoothly approximable? Is it because the random graph is not represented as a union of finite homogeneous substructures?

1. Note that in https://arxiv.org/pdf/2005.12341.pdf by DANIEL WOLF it is written "We define ‘homogeneous substructure’ as one term, not as the conjunction of two words; that is, ‘homogeneous substructure’ does not mean a substructure that is homogeneous."

Answer 1

A graph $G$ is homogeneous if for any finite induced subgraphs $A,B\subseteq G$, any isomorphism $A\to B$ extends to an automorphism of $G$.

Suppose for contradiction that the random graph $R$ is smoothly approximable, witnessed by the an ascending chain $G_0\subseteq G_1\subseteq G_2\subseteq \dots \subseteq R$ of finite induced subgraphs. I claim that each $G_i$ is a homogeneous graph.

Indeed, for each $i$, suppose $A,B\subseteq G_i$ are finite induced subgraphs and $\sigma\colon A\to B$ is an isomorphism. Let $a$ be a tuple enumerating $A$, and let $b$ be a tuple enumerating $B$, so that $\sigma(a) = b$. Then the tuples $a$ and $b$ have the same quantifier-free type in $R$, and hence $\mathrm{tp}_R(a) = \mathrm{tp}_R(b)$ by quantifier elimination for $\mathrm{Th}(R)$. Thus there is an automorphism $\sigma'$ of $R$ such that $\sigma'(a) = b$ and $\sigma'(G_i) = G_i$. So $\sigma'|_{G_i}$ is an automorphism of $G_i$ extending $\sigma$, and $G_i$ is homogeneous.

Now the finite homogeneous graphs were classified by Gardiner in 1976. They are:

• The pentagon $C_5$.
• A graph called $L(K_{3,3})$, the line graph of the complete bipartite graph $K_{3,3}$.
• A disjoint union of $k$ copies of the complete graph $K_n$ for some finite $k$ and $n$.
• The edge complement of the previous example, which is the complete $k$-partite graph, in which each piece has the same finite size $n$.

Finally, one checks that $R$ cannot be written as a union of an increasing chain of graphs from the above list (which all must be isomorphic to the disjoint union of $K_n$ or the complete $n$-partite graph, once they are bigger than the exceptional graphs $C_5$ and $L(K_{3,3})$.