---
abstract: 'We prove the monadic second order 0-1 law for two recursive tree models: uniform attachment tree and preferential attachment tree. We also show that the first order 0-1 law does not hold for non-tree uniform attachment models.'
address:
- Moscow Institute of Physics and Technology
- Moscow Institute of Physics and Technology
author:
- 'Y.A. Malyshkin'
- 'M.E. Zhukovskii'
title: 'MSO 0-1 law for recursive random trees'
---

Introduction
============

Let $n\in\mathbb{N}$. [*A random graph $\mathcal{G}_n$*]{} is a random element of the set of all undirected graphs without loops and multiple edges on the vertex set $[n]:=\{1,\ldots,n\}$ with a probability distribution $\mu_n$. The case of the uniform distribution $\mu_n$ is widely studied as a particular case of [*the binomial random graph*]{} denoted by $G(n,p)$ [@Bollobas; @Janson] where every edge appears independently with probability $p$ (i.e., $\mu_n(G)=p^{|E(G)|}(1-p)^{{n\choose 2}-|E(G)|}$ for every graph $G$ on vertex set $[n]$). Hereinafter, we denote by $V(G)$ and $E(G)$ the set of vertices and the set of edges of $G$ respectively.

Let us recall that [*a first order (FO) sentence*]{} about graphs expresses a graph property using the following symbols: variables $x,y,x_1,\ldots$, logical connectives $\wedge,\vee,\neg,\Rightarrow,\Leftrightarrow$, predicates $\sim$ (adjacency), $=$ (coincidence), quantifiers $\exists,\forall$ and brackets (see the formal definition in, e.g., [@Libkin; @Survey; @Strange]). For example, the property of being complete is expressed by the FO sentence $$\forall x\forall y\quad [\neg(x=y)]\Rightarrow[x\sim y].$$ A random graph $\mathcal{G}_n$ obeys [*FO 0-1 law*]{} if, for every FO sentence $\varphi$, ${\sf P}(\mathcal{G}_n\models\varphi)$ approaches either 0 or 1 as $n\to\infty$. Following traditions of model theory, we write $G\models\varphi$ when $\varphi$ is true on $G$. Study of 0-1 laws for random graph models is closely related to questions about expressive power of formal logics which, in turn, have applications in complexity [@Libkin; @Verb]. In 1969 Glebskii, Kogan, Liogon’kii, Talanov [@Glebsk] (and independently Fagin in 1976 [@Fagin]) proved that $G(n,\frac{1}{2})$ (i.e., $\mu_n$ is uniform) obeys FO 0-1 law. In [@Spencer_Ehren], Spencer proved that, for $p=p(n)$ such that, for every $\alpha>0$, $\min\{p,1-p\}n^{\alpha}\to\infty$ as $n\to\infty$, $G(n,p)$ obeys FO 0-1 law as well. The sparse case $p=n^{-\alpha}$, $\alpha>0$, was studied in [@Shelah].

[*Monadic second order (MSO) logic*]{} is an extension of the FO logic [@Libkin Definition 7.2]. Sentences in this logic are built of the same symbols and, additionally, variable unary predicates $X,Y,X_1,\ldots$. For example, the property of being disconnected is expressed by the MSO sentence $$\exists X\quad(\exists x\,X(x))\wedge(\exists x\,\neg X(x))\wedge(\forall x\forall y\,[X(x)\wedge \neg X(y)]\Rightarrow[\neg(x\sim y)]).$$ In the same way, $\mathcal{G}_n$ obeys [*MSO 0-1 law*]{} if, for every MSO sentence $\varphi$, ${\sf P}(\mathcal{G}_n\models\varphi)$ approaches either 0 or 1 as $n\to\infty$. In 1985 [@Kaufmann] Kaufmann and Shelah proved that $G(n,\frac{1}{2})$ does not obey MSO 0-1 law. The same is true for all other constant $p\in(0,1)$ and $p=n^{-\alpha}$, $\alpha\in(0,1]\cup\{1+1/\ell,\,\ell\in\mathbb{N}\}$ (see [@Zhuk_Ostr_APAL; @Tyszkiewicz; @Zhuk_JML]).

Further, many other random graph models were studied in the context of logical limit laws. Let us list some of them. In [@McColm], it was proven that the labeled uniform random tree ($\mu_n(T)=n^{2-n}$ for every tree $T$ on vertex set $[n]$) obeys MSO 0-1 law. The FO behavior of random regular graphs was studied in [@Haber]. In [@geo], logical laws were proven for random geometric graphs. In [@Muller], FO and MSO 0-1 laws were studied for minor-closed classes of graphs. In [@Zhuk_Svesh], FO 0-1 laws were proven for the classical uniform random graph model $G(n,m)$ ($m$ edges are chosen uniformly at random). Finally, some results related to FO behavior of preferential attachment random graph model were obtained in [@Kleinberg].

In this paper, we study the logical behavior of two well-known recursive random graph models: uniform model and preferential attachment model [@recursive]. Let $m\in\mathbb{N}$. The uniform attachment random graph $G^{\mathrm{U}}(n,m)$ is defined recursively: $G^{\mathrm{U}}(m+1,m+1)$ is complete graph on $[m+1]$; for every $n\geq m+1$, $G^{\mathrm{U}}(n+1,m)$ is obtained from $G^{\mathrm{U}}(n,m)$ by adding the vertex $n+1$ with $m$ edges going from $n+1$ to vertices from $[n]$ chosen uniformly at random: $$\begin{aligned}
 {\sf P}\biggl(n+1\sim x_1,\ldots,n+1\sim x_m\text{ in }G^{\mathrm{U}}(n+1,m)\biggr)={n\choose m}^{-1},\\ 1\leq x_1<\ldots<x_m\leq n.\end{aligned}$$ In Section \[no\_law\], we show that, for every $m\geq 2$, $G^{\mathrm{U}}(n,m)$ does not obey FO 0-1 law. For $m=1$, we prove the following positive result.

$G^{\mathrm{U}}(n,1)$ obeys MSO 0-1 law.

In the preferential attachment random graph $G^{\mathrm{P}}(n,m)$, we also start from the complete graph $G^{\mathrm{P}}(m+1,m+1)$. $G^{\mathrm{P}}(n+1,m)$ is also obtained from $G^{\mathrm{P}}(n,m)$ by adding the vertex $n+1$ with $m$ edges going from $n+1$ to vertices from $[n]$. The only difference is that these edges $e_1,\ldots,e_m$ are drawn independently, each one has distribution ${\sf P}(e_i=\{n+1,v\})=\frac{\mathrm{deg}_{G^{\mathrm{P}}(n,m)}v}{2mn}$, $v\in[n]$. Notice that this graph may have multiple edges in contrast to all the previous. This can be fixed by requiring $e_i$, $i\in[m]$, to connect $n+1$ with a vertex that do not belong to none of $e_1,\ldots,e_{i-1}$. Notice that this modification does not change the model when $m=1$. In [@Kleinberg], it was proven that $G^{\mathrm{P}}(n,m)$ does not obey FO 0-1 law for every $m\geq 3$. The same proof works for the modification of the model that avoids multiple edges. In this paper, we prove that MSO 0-1 law holds for $m=1$.

$G^{\mathrm{P}}(n,1)$ obeys MSO 0-1 law.

Unfortunately, the question about validity of both FO and MSO 0-1 law for $G^{\mathrm{P}}(n,2)$ remains open.

FO 0-1 law fails for uniform model when $m\geq 2$ {#no_law}
=================================================

Let us first assume that $m=2$. Let $X_n$ be the number of [*diamond graphs*]{} (graph with 4 vertices and 5 edges) in $G^{\mathrm{U}}(n,2)$. Trivially, we get $${\sf E}X_n=3\left(\sum_{4\leq u_1<u_2\leq n}\frac{1}{{{u_1-1}\choose 2}{{u_2-1}\choose 2}}\right)+
2\left(\sum_{v=4}^{n-2}\sum_{v+1\leq u_1<u_2\leq n}\frac{1}{{{u_1-1}\choose 2}{{u_2-1}\choose 2}}\right)\to\beta$$ where $\beta>0$ is finite.

Fix $k>3$. Let $g(k)$ be the maximum value of $X_k$, i.e. ${\sf P}(X_k=g(k))>0$ while ${\sf P}(X_k>g(k))=0$. Obviously, $g(k)={{k-2}\choose 2}$. We get $${\sf P}(X_n\geq g(k))>{\sf P}(X_k=g(k))>0.
\label{non_conv_below}$$ Fix $\varepsilon>0$ and choose $k$ in a way such that $\frac{\beta}{g(k)}<1-\varepsilon$. Then, for $n$ large enough, $${\sf P}(X_n\geq g(k))\leq\frac{{\sf E}X_n}{g(k)}<1-\frac{\varepsilon}{2}.
\label{non_conv_above}$$ As the property of having at least $g(k)$ diamond graphs is expressible in FO, we get that $G^{\mathrm{U}}(n,2)$ does not obey FO 0-1 law.\
Now, let $m\geq 3$. Let $X_n$ be the number of $K_{m+1}$ (complete graphs on $m+1$ vertices) in $G^{\mathrm{U}}(n,m)$. Then, for some $\beta$ (below, we set ${i\choose j}:=1$ when $0\leq i<j$), $${\sf E}X_n=\sum_{1\leq u_1<\ldots<u_m<v\leq n}\frac{{{u_2-2}\choose {m-1}}}{{{u_2-1}\choose m}}\frac{{{u_3-3}\choose {m-2}}}{{{u_3-1}\choose m}}\ldots
\frac{{{u_m-m}\choose 1}}{{{u_m-1}\choose m}}\frac{1}{{{v-1}\choose m}}\to\beta.$$

The rest of the proof is the same as in the case $m=2$. For $k>m+1$, $g(k)=k-m$ is the maximum value of $X_k$. Choose $k$ in a way such that $\frac{\beta}{g(k)}<1-\varepsilon$. In the same way, relations (\[non\_conv\_below\]) and (\[non\_conv\_above\]) hold. Therefore, $G^{\mathrm{U}}(n,m)$ does not obey FO 0-1 law.\

Proofs
======

For a tree $G$ and its vertex $R$, we denote by $G_R$ the tree $G$ rooted in $R$. Rooted trees $G_u$ and $H_v$ are [*isomorphic*]{} (denoted by $G_u\cong H_v$) if there exists a bijection $f:V(G_u)\to V(H_v)$ that preserves the child–parent relation: $a$ is a child of $b$ in $G_u$ if and only if $f(a)$ is a child of $f(b)$ in $H_v$.

Given a tree $\mathcal{T}$ and a rooted tree $G_R$, we say that [*$\mathcal{T}$ has a pendant $G_R$*]{}, if there is an edge $\{u,v\}$ in $\mathcal{T}$ such that, after its deletion, the component $F$ of $\mathcal{T}$ containing $v$ is such that $F_v\cong G_R$.\
We will use the following claim proved in [@McColm] (hereinafter, given a graph property $P$, we say that $\mathcal{G}_n$ has $P$ [*with high probability*]{}, if $\mu_n(P)\to 1$ as $n\to\infty$).

[[@McColm Theorem 2.1]]{} Let $\mathcal{G}_n$ be a random tree (i.e. $\mu_n$ is positive only on trees). Let, for every rooted tree $G_R$, with high probability $\mathcal{G}_n$ has a pendant $G_R$. Then $\mathcal{G}_n$ obeys MSO 0-1 law. \[the\_tool\]

MSO 0-1 law for uniform recursive tree
--------------------------------------

By Claim \[the\_tool\], it is sufficient to prove that, for every rooted $G_R$, $G^{\mathrm{U}}(n,1)$ contains a pendant $G_R$ with high probability.

Consider an arbitrary rooted tree $G_R$. Let $v$ be the number of vertices of $G_R$. Let $R=j_1<\ldots<j_v$ be a labelling of vertices of $G_R$ such that, for every $s\in\{2,\ldots,v\}$, $j_s$ is adjacent to $j_{s-1}$.

Let $n_0,r\in\mathbb{N}$ be such that $n_0+r+v\leq n$. Let $n_0+r<i_1<\ldots<i_v\leq n$. Let $B_{i_1,...,i_v}(n_0,r,n)$ denote the event that, in $G^{\mathrm{U}}(n,1)$, deletion of the edge $\{n_0,i_1\}$ divide the tree into two connected components such that one of them (denote it by $H$) consists of $i_1,\ldots,i_v$ and the bijection $j_s\to i_s$, $s\in\{1,\ldots,v\}$, is an isomorphism of $G_R$ and $H_{i_1}$. Let $$\tilde B_{i_1,\ldots,i_v}(n_0,n)=\bigsqcup_{\ell=0}^{r-1}B_{i_1,\ldots,i_v}(n_0+\ell,r-\ell,n),$$ $$X:=X(n_0,n)=\sum_{n_0+r<i_1<\ldots<i_v\leq n}I_{\tilde B_{i_1,...,i_v}(n_0,n)}.$$ Notice that the event $\{X>0\}$ implies existence of a pendant $G_R$ in $G^{\mathrm{U}}(n,1)$. So, it is sufficient to prove that for every $\varepsilon>0$ there exists $r\in\mathbb{N}$ such that ${\sf P}(X>0)>1-\varepsilon$ for all large enough $n$.

Clearly, $${\sf P}(B_{i_1,...,i_v}(n_0,r,n))=\frac{1}{(n-v)\ldots(n-1)},$$ $${\sf P}(\tilde B_{i_1,...,i_v}(n_0,n))=\frac{r}{(n-v)\ldots(n-1)}.$$ Therefore, $${\sf E}X={n-n_0-r\choose v}\frac{r}{(n-v)\ldots(n-1)}\to \frac{r}{v!},\quad n\to\infty.$$

For distinct sets $(i_1,\ldots,i_v)$ and $(\tilde i_1,\ldots,\tilde i_v)$, the events $\tilde B_{i_1,...,i_v}(n_0,n)$ and $\tilde B_{\tilde i_1,...,\tilde i_v}(n_0,n)$ are disjoint if $\{i_1,\ldots,i_v\}\cap\{\tilde i_1,\ldots,\tilde i_v\}\neq\varnothing$. Otherwise, $${\sf P}(\tilde B_{i_1,...,i_v}(n_0,n)\cap \tilde B_{\tilde i_1,...,\tilde i_v}(n_0,n))=\frac{r^2}{(n-2v)\ldots(n-1)}.$$ Therefore, $$\begin{aligned}
\mathrm{Var}X&\!=\!{n\!-\!n_0\!-\!r\choose v}\!\left(\frac{r}{(n-v)\ldots(n-1)}-\left(\frac{r}{(n-v)\ldots(n-1)}\right)^2\right)\\
 &\!+\!{n\!-\!n_0\!-\!r\choose v}\!{n\!-\!n_0\!-\!r\!-\!v\choose v}\!\left(\!\frac{r^2}{(n\!-\!2v)\!\ldots\!(n\!-\!1)}\!-\!\left(\frac{r}{(n\!-\!v)\!\ldots\!(n\!-\!1)}\right)^2\right)\\
 &\!=\!{n\!-\!n_0\!-\!r\choose v}\frac{r}{(n-v)\ldots(n-1)}+O\left(\frac{1}{n}\right)\to\frac{r}{v!},\quad n\to\infty.\end{aligned}$$ It remains to apply Chebyshev’s inequality: $${\sf P}(X=0)\leq\frac{\mathrm{Var}X}{({\sf E}X)^2}\to\frac{v!}{r},\quad n\to\infty.$$

MSO 0-1 law for preferential attachment random tree
---------------------------------------------------

As above, here, we prove that, for every rooted $G_R$, $G^{\mathrm{P}}(n,1)$ contains a pendant $G_R$ with high probability.

In the same way, we consider a labelling $R=j_1<\ldots<j_v$ of vertices of $G_R$ such that, for every $s\in\{2,\ldots,v\}$, $j_s$ is adjacent to $j_{s-1}$.

Let $i_1<\ldots<i_v\leq n$. Let $B_{i_1,...,i_v}(n)$ denote the event that, in $G^{\mathrm{P}}(n,1)$, there exists a vertex $n_0<i_1$ such that deletion of the edge $\{n_0,i_1\}$ divide the tree into two connected components $H$ and $G^{\mathrm{P}}(n,1)\setminus H$ such that $H$ is induced by $i_1,\ldots,i_v$ and the bijection $j_s\to i_s$, $s\in\{1,\ldots,v\}$, is an isomorphism of $G_R$ and $H_{i_1}$. Let $$X=X(n)=\sum_{2\leq i_1<\ldots<i_v\leq n}I_{B_{i_1,...,i_v}(n)}.$$ As above, the event $\{X>0\}$ implies existence of a pendant $G_R$ in $G^{\mathrm{P}}(n,1)$.

Notice that, for every $\nu\in\{1,\ldots,v\}$, and $i_\nu<s<i_{\nu+1}$ (hereinafter, $i_{v+1}=n+1$), the probability that $s$ is not adjacent to any of $i_1,\ldots,i_\nu$ in $G^{\mathrm{P}}(n,1)$ equals $1-\frac{2\nu-1}{2(s-1)}$.

For $\ell\in\{2,\ldots,v\}$, let $x_\ell$ be the neighbor of $j_{\ell}$ in the induced subgraph $G_R|_{\{j_1,\ldots,j_{\ell}\}}$. Denote $d_\ell\!=\!\mathrm{deg}_{G_R|_{\{j_1,\ldots,j_{\ell-1}\}}}x_{\ell}$ if $x_{\ell}\!\neq\! j_1$ and $d_\ell\!=\!\mathrm{deg}_{G_R|_{\{j_1,\ldots,j_{\ell-1}\}}}x_{\ell}+1$ if $x_{\ell}=j_1$. Set $D:=\prod_{\ell=2}^{v}d_{\ell}$.

Clearly, $$\begin{aligned}
{\sf P}(B_{i_1,...,i_v}(n))&=D\left[\prod_{\ell=2}^{v}\frac{1}{2(i_\ell-1)}\right]\\
&\times\left[\prod_{\ell=1}^v\frac{(2i_{\ell}+2-2\ell)(2i_{\ell}+4-2\ell)\ldots(2i_{\ell+1}-2-2\ell)}{(2i_{\ell}+1)(2i_{\ell}+3)\ldots(2i_{\ell+1}-3)}\right]\\
&=\frac{D}{2^{v-1}}\sqrt{\frac{i_1}{n^{2v-1}}}\left(1+O\left(\frac{1}{i_1}\right)\right).\end{aligned}$$ Therefore, $$\begin{aligned}
 {\sf E}X&=\sum_{1\leq i_1<\ldots<i_v\leq n}{\sf P}\left(B_{i_1,...,i_v}(n)\right)\\
&=\frac{D}{2^{v-1}}\sum_{i_1=1}^{n-v+1}\sqrt{\frac{i_1}{n^{2v-1}}}{n-i_1\choose v-1}\left(1+O\left(\frac{1}{i_1}\right)\right)\\
&=\frac{D}{(v-1)!2^{v-1}}\sum_{i_1=1}^{n-v+1}\sqrt{\frac{i_1}{n}}\left(1-\frac{i_1}{n}\right)^{v-1}\left(1+O\left(\frac{1}{i_1}\right)+O\left(\frac{1}{n-i_1}\right)\right)\\
 &\sim\frac{2Dn}{(2v+1)!!},\quad n\to\infty.\end{aligned}$$

For distinct sets $(i_1,\ldots,i_v)$, $(\tilde i_1,\ldots,\tilde i_v)$, the events $B_{i_1,...,i_v}(n)$ and $B_{\tilde i_1,...,\tilde i_v}(n)$ are disjoint if $\{i_1,\ldots,i_v\}\cap\{\tilde i_1,\ldots,\tilde i_v\}\neq\varnothing$. Otherwise, assume that $i_1<\tilde i_1$ and let $\nu\in\{1,\ldots,v\}$ be such that $i_{\nu}<\tilde i_1<i_{\nu+1}$. Let $(\sigma_1,\ldots,\sigma_{2v})$ be the permutation of $(i_{1},\ldots,i_v,\tilde i_1,\ldots,\tilde i_v)$ such that $\sigma_1<\ldots<\sigma_{2v}$. Then, letting $\sigma_{2v+1}=n+1$, we get $$\begin{aligned}
{\sf P}(B_{i_1,...,i_v}(n)\!\cap\! B_{\tilde i_1,...,\tilde i_v}(n))&=D^2\left[\prod_{\ell=2}^{v}\frac{1}{2(i_\ell-1)}\right]\times\left[\prod_{\ell=2}^{v}\frac{1}{2(\tilde i_\ell-1)}\right]\\
&\times\!\left[\prod_{\ell=1}^{\nu}\frac{(2\sigma_{\ell}\!+\!2\!-\!2\ell)(2\sigma_{\ell}\!+\!4\!-\!2\ell)\ldots(2\sigma_{\ell+1}\!-\!2\!-\!2\ell)}{(2\sigma_{\ell}\!+\!1)(2\sigma_{\ell}\!+\!3)\!\ldots\!(2\sigma_{\ell+1}\!-\!3)}\right]\\
&\times\!\left[\prod_{\ell=\nu+1}^{2v}\!\frac{(2\sigma_{\ell}\!+\!3\!-\!2\ell)\!(2i\sigma{\ell}\!+\!5\!-\!2\ell)\!\ldots\!(2\sigma_{\ell+1}\!-\!1\!-\!2\ell)}{(2\sigma_{\ell}\!+\!1)\!(2\sigma_{\ell}\!+\!3)\!\ldots\!(2\sigma_{\ell+1}\!-\!3)}\right]\\
&=\frac{D^2}{2^{2(v-1)}}\frac{\sqrt{i_1\tilde i_1}}{n^{2v-1}}\left(1+O\left(\frac{1}{i_1}\right)\right)\\
&={\sf P}(B_{i_1,...,i_v}(n)){\sf P}(B_{\tilde i_1,...,\tilde i_v}(n))\left(1+O\left(\frac{1}{i_1}\right)\right).\end{aligned}$$

Therefore, $$\begin{aligned}
\mathrm{Var}X&<{\sf E}X\\
&+\!2\!\!\sum_{{\scriptsize \substack{i_1\!<\!\ldots\!<\!i_v \\ i_1\!<\!\tilde i_1\!<\!\ldots\!<\!\tilde i_v}}}\!\!\left[{\sf P}(B_{i_1,...,i_v}(n)\!\cap\! B_{\tilde i_1,...,\tilde i_v}(n))\!-\!{\sf P}(B_{i_1,...,i_v}(n)){\sf P}(B_{\tilde i_1,...,\tilde i_v}(n))\right]\\
&<{\sf E}X+2{\sf E}X\sum_{i_1<\ldots<i_v}{\sf P}(B_{i_1,...,i_v}(n))O\left(\frac{1}{i_1}\right)
=O(n).\\\end{aligned}$$ Finally, $${\sf P}(X=0)\leq\frac{\mathrm{Var}X}{({\sf E}X)^2}\to 0,\quad n\to\infty.$$

[99]{}

B. Bollobás, [*Random Graphs*]{}, 2nd Edition, Cambridge University Press, 2001.

B. Bollobás, O. Riordan, J. Spencer, G. Tusnády, [*The degree sequence of a scale-free random graph process*]{}. Random Structures & Algorithms, 2001, [**18**]{}(3): 279–290.

Y. V. Glebskii, D. I. Kogan, M. I. Liogon’kii, V. A. Talanov. [*Range and degree of realizability of formulas in the restricted predicate calculus*]{}. Cybernetics and Systems Analysis, 1969, [**5**]{}(2): 142–154. (Russian original: Kibernetika, 1969, [**5**]{}(2): 17–27).

R. Fagin. [*Probabilities in finite models.*]{} J. Symbolic Logic, 1976, [**41**]{}: 50–58.

S. Haber, M. Krivelevich M. [*The logic of random regular graphs*]{}. J. Comb., 2010, [**1**]{}(3-4): 389–440.

P. Heinig, T. Muller, M. Noy, A. Taraz, [*Logical limit laws for minor-closed classes of graphs*]{}, Journal of Combinatorial Theory, Series B. 2018, [**130**]{}: 158–206.

S. Janson, T. Luczak, A. Rucinski, [*Random Graphs*]{}, New York, Wiley, 2000.

M. Kaufmann, S. Shelah. [*On random models of finite power and monadic logic*]{}. Discrete Mathematics, 1985, [**54**]{}(3): 285–293.

R. D. Kleinberg, J. M. Kleinberg. [*Isomorphism and embedding problems for infinite limits of scale-free graphs*]{}. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pages 277–286, 2005.

L. Libkin. [*Elements of finite model theory*]{}. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag Berlin Heidelberg. 2004.

G.L. McColm. [*First order zero-one laws for random graphs on the circle.*]{} Random Structures and Algorithms, [**14**]{}(3): 239–266, 1999.

G.L. McColm. [*MSO zero-one laws on random labelled acyclic graphs*]{}. Discrete Mathematics, 2002, [**254**]{}: 331–347.

L.B. Ostrovsky, M.E. Zhukovskii. [*Monadic second-order properties of very sparse random graphs.*]{} Annals of pure and applied logic. 2017, [**168**]{}(11): 2087–2101.

A.M. Raigorodskii, M.E. Zhukovskii. [*Random graphs: models and asymptotic characteristics*]{}, Russian Mathematical Surveys, [**70**]{}(1): 33–81, 2015.

J.H. Spencer. [*Threshold spectra via the Ehrenfeucht game.*]{} Discrete Applied Math., 1991, [**30**]{}: 235–252.

S. Shelah, J.H. Spencer. [*Zero-one laws for sparse random graphs.*]{} J. Amer. Math. Soc., 1988, [**1**]{}: 97–115.

J.H. Spencer, [*The Strange Logic of Random Graphs*]{}, Springer Verlag, 2001.

N.M. Sveshnikov, M.E. Zhukovskii, [*First order zero-one law for uniform random graphs*]{}, Sbornik Mathematics, 2020, [**211**]{}, https://doi.org/10.1070/SM9321.

O. Verbitsky, M. Zhukovskii. [*The Descriptive Complexity of Subgraph Isomorphism Without Numerics*]{}, Lecture Notes in Computer Science, International Computer Science Symposium in Russia. 2017. P. 308–322.

J. Tyszkiewicz, [*On Asymptotic Probabilities of Monadic Second Order Properties*]{}, Lecture Notes in Computer Science, 1993, [**702**]{}: 425–439.

S. Shelah, J.H. Spencer, *Zero-one laws for sparse random graphs*, J. Amer. Math. Soc., 1988, **1**:97–115.

M.E. Zhukovskii, [*Logical laws for short existential monadic second-order sentences about graphs*]{}, Journal of Mathematical Logic, 2019, https://doi.org/10.1142/S0219061320500075.
