3
$\begingroup$

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."
$\endgroup$
6
  • $\begingroup$ Welcome to MS. (Do not mind the comment of the Bot, your question is definitely clearer than average.) $\endgroup$ Commented May 17, 2023 at 11:24
  • $\begingroup$ Example 1.18 in these note proves the pseudofiniteness of the random graph modvac18.math.ens.fr/slides/Garcia.pdf $\endgroup$ Commented May 17, 2023 at 11:39
  • $\begingroup$ 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. $\endgroup$ Commented May 17, 2023 at 12:04
  • $\begingroup$ Interesting question! The random bipartite graph is not smoothly approximable. What about the random graph? I don't know. $\endgroup$ Commented May 17, 2023 at 14:42
  • $\begingroup$ In this article Hrushovski proves that the random graph comes close (but not quite!) to be smoothly approximable. $\endgroup$ Commented May 17, 2023 at 15:58

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Commented Mar 15 at 18:49
  • $\begingroup$ @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. $\endgroup$ Commented Mar 15 at 18:55
  • $\begingroup$ @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. $\endgroup$ Commented Mar 15 at 18:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .