# On pseudofiniteness and smoothly approximability

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."
• Welcome to MS. (Do not mind the comment of the Bot, your question is definitely clearer than average.) Commented May 17, 2023 at 11:24
• Example 1.18 in these note proves the pseudofiniteness of the random graph modvac18.math.ens.fr/slides/Garcia.pdf Commented May 17, 2023 at 11:39
• Thank you! But I know about pseudofiniteness of a random graph. I would like to know about the smooth approximability of a random graph. It seems to me that a random regular graph en.wikipedia.org/wiki/Random_regular_graph is just a smoothly approximable one. Commented May 17, 2023 at 12:04
• Interesting question! The random bipartite graph is not smoothly approximable. What about the random graph? I don't know. Commented May 17, 2023 at 14:42
• In this article Hrushovski proves that the random graph comes close (but not quite!) to be smoothly approximable. Commented May 17, 2023 at 15:58

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})$$.

• Dear Alex, thanks for the extended answer. I'm confused once again. It seems that Daniel and his supervisor Professor Dugald MacPherson told me personally that a homogeneous substructure is different from a homogeneous structure. In the work pages.uoregon.edu/kantor/PAPERS/aleph0categorical.pdf it is proved that the bipartite random graph is not smoothly approximable (Example, p.457). What can you say about the smooth approximability of a random regular graph en.wikipedia.org/wiki/Random_regular_graph? Commented Mar 15 at 18:49
• @MarkhabatovNurlan Indeed, "$N$ is a homogeneous substructure of $M$" has a different definition from "$N$ is a substructure of $M$ and $N$ is a homogeneous structure", as pointed out in the paper by Daniel Wolf that you referenced in the question. What I have shown in my answer is that if $N$ is a homogeneous substructure of $M$ and $\mathrm{Th}(M)$ has quantifier elimination, then $N$ is a homogeneous structure. The converse is not true in general. So my answer does not contract the correct things you were told by Wolf and MacPherson. Commented Mar 15 at 18:55
• @MarkhabatovNurlan The wikipedia page on random regular graphs that you linked to describes a probability measure on finite regular graphs, but "smoothly approximable" is a property of a fixed countably infinite structure. So I don't know how to make sense of your question. Commented Mar 15 at 18:59