11institutetext: Laboratoire de Combinatoire et d’Informatique Mathématique,
Université du Québec à Montréal,
CP 8888 Succ. Centre-ville, Montréal (QC) Canada H3C 3P8

# The characteristic sequence of the integers that are the sum of two squares
is not morphic

Shuo Li

###### Abstract

Let $(s_{2}(n))_{n\in\mathbb{N}}$ be a $0,1$-sequence such that, for any
natural number $n$, $s_{2}(n)=1$ if and only if $n$ is a sum of two squares.
In a recent article, Tahay proved that the sequence
$(s_{2}(n))_{n\in\mathbb{N}}$ is not $k$-automatic for any integer $k$, and
asked if this sequence can be morphic. In this note, we give a negative answer
to this question.

##  1 Introduction

For any integer $k\geq 1$, let us define the $0,1$-sequence
$(s_{k}(n))_{n\in\mathbb{N}}$ such that, for any $n\in\mathbb{N}$,
$s_{k}(n)=1$ if $n$ can be written as a sum of $k$ squares and $s_{k}(n)=0$ if
not. From the definition, the sequence $(s_{1}(n))_{n\in\mathbb{N}}$
characterizes all squares in $\mathbb{N}$, while $(s_{2}(n))_{n\in\mathbb{N}}$
and $(s_{3}(n))_{n\in\mathbb{N}}$ characterize respectively the sequences
A001481 and A004215 in OEIS [13]. It is conjectured by Bachet and proved by
Lagrange in 1770 that every natural number can be written as a sum of four
squares. Thus, $(s_{k}(n))_{n\in\mathbb{N}}$ is a constant sequence of $1$ for
any $k\geq 4$. The automaticity and the morphicity of
$(s_{k}(n))_{n\in\mathbb{N}}$ for $k=1,2,3$ are discussed in [15], where the
notion of automaticity and the morphicity will be given in Section 2. The
$2$-automaticity of $(s_{3}(n))_{n\in\mathbb{N}}$ is proven in [4] and the
non-automaticity of $(s_{1}(n))_{n\in\mathbb{N}}$ is proven in [12] [14]. In
[15], Tahay proved that $(s_{1}(n))_{n\in\mathbb{N}}$ is morphic and
$(s_{2}(n))_{n\in\mathbb{N}}$ is not automatic. Notice that the non-
automaticity of $(s_{2}(n))_{n\in\mathbb{N}}$ can also be established from the
results in [8]. However, the morphicity of $(s_{2}(n))_{n\in\mathbb{N}}$
remains open.

In this note, we first give a criterion of the non-morphicity of a sequence,
then prove non-morphicity of $(s_{2}(n))_{n\in\mathbb{N}}$ as an application
of this criterion, which answers a question of Tahay asked in [15]. Moreover,
using the same criterion, we prove the non-morphicity of
$(s^{\prime}_{2}(n))_{n\in\mathbb{N}}$, which characterize the integers that
are the sum of two non-zero squares.

Notice that the sequence $(s_{2}(n))_{n\in\mathbb{N}}$ is multiplicative (see,
for example [15]). By multiplicative, we mean, for any pair of coprime
integers $(p,q)$, one has $s_{2}(p)s_{2}(q)=s_{2}(pq)$. The (non)-automaticity
of (completely) multiplicative sequences has been intensively studied during
the recent years, for example, [5] [1] [11] [7] [6] [8] [9], while the
(non)-morphicity of (completely) multiplicative sequences, from the author’s
knowledge, is rarely studied in the literature. This note gives an example to
show the non-morphicity of a multiplicative sequence.

##  2 Definitions and notation

By _alphabet_ , we mean a finite set. Its elements are called _letters_. Let
$A^{*}$ denote the free monoid generated by $A$ under concatenations having
neutral element the empty word $\varepsilon$. For any word
$w=w_{0}w_{1}w_{2}\cdots w_{n-1}\in A^{*}$, the _length_ of $w$ is the integer
$|w|=n$. The length of any _infinite words_ is infinite. For any letter $a\in
A$, let $|w|_{a}$ denote the number of occurrences of the letter $a$ in $w$. A
_prefix_ of a word $w=w_{0}w_{1}w_{2}\cdots$ is a finite string
$w_{0}w_{1}w_{2}\cdots w_{t}$ such that $t\leq|w|$. For any pair of integers
$i\leq j$, let $w[i,j]=w_{i}w_{i+1}\cdots w_{j}$.

Let $A$ and $B$ be two alphabets. A _morphism_ $\phi$ is a map $A^{*}\to
B^{*}$ satisfying $\phi(xy)=\phi(x)\phi(y)$ for any pair of elements $x,y$ in
$A^{*}$. The morphism $\phi$ is called _$k$ -uniform_ if for all elements
$a\in A$, $|\phi(a)|=k$, and it is called _non-uniform_ otherwise. A morphism
$\phi$ is called a _coding_ function if it is $1$-uniform, and it is called
_non-erasing_ if $\phi(a)\neq\varepsilon$ for all $a\in A$. For any positive
integer $k$, by $\phi^{k}$, we mean the composition of $k$ times of the
morphism $\phi$. Particularly, $\phi^{0}$ is the identity function.

Let $A$ be a finite alphabet, and let $(a_{n})_{n\in\mathbb{N}}$ be an
infinite sequence over $A$. It is called _morphic_ if there exists an alphabet
$B$, a letter $b\in B$, a word $w\in B^{*}$, a non-erasing morphism
$\phi:B^{*}\to B^{*}$, and a coding function $\psi:B\to A$, such that
$\phi(b)=bw$ and

$(a_{n})_{n\in\mathbb{N}}=\lim_{i\to\infty}\psi(\phi^{i}(b)).$

Moreover, for any positive integer $k\geq 2$, the sequence
$(a_{n})_{n\in\mathbb{N}}$ is called _$k$ -automatic_ if $\phi$ is
$k$-uniform, is called _automatic_ if $\phi$ is $k$-uniform for some integer
$k\geq 2$, and it is called _non-automatic_ if it is not $k$-uniformly morphic
for any integer $k\geq 2$.

##  3 Non-morphicity of sequences

The purpose of this section is to prove the following theorem:

###### Theorem 1

Let $(a_{n})_{n\in\mathbb{N}}$ be a morphic sequence over the alphabet $A$. If
there exists $a\in A$ and two positive numbers $0<\gamma<1$, $C>0$ such that

$|a[0,N]|_{a}\sim C\frac{N}{(\log(N))^{\gamma}},$

then $(a_{n})_{n\in\mathbb{N}}$ is not morphic.

###### Proposition 2

For any alphabet $A$ and any morphism $\phi:A^{*}\to A^{*}$, if there exists
$a\in A$ and $w\in A^{*}$ such that $\phi(a)=aw$, then there exist real
numbers $\alpha\geq 1$, $G>0$ and non-negative integers $l$ and $T\geq 1$ such
that

$|\phi^{Tk}(a)|\sim G(Tk)^{l}\alpha^{Tk}.$

Moreover, for any $b\in A$, there exist real numbers $\beta\leq\alpha$,
$G^{\prime}>0$, a non-negative integer $m$ and finitely many complex numbers
$\beta_{1},\beta_{2},\cdots,\beta_{s}$ such that $|\beta_{i}|=\beta$ for all
$i$ and that

$|\phi^{Tk}(a)|_{b}\sim G^{\prime}(Tk)^{m}\sum_{i=1}^{s}\beta_{i}^{Tk}.$

Moreover, if $\beta=\alpha$, then there exists a unique real number
$\beta_{1}=\beta$.

###### Proof

The first part a direct consequence of Remark 1 and Proposition 4.1 in [3].
For the second part, from Corollary 8.2.3 in [2], there exists a $d\times d$
matrix $M$, known as the incidence matrix of the morphism $\phi$ (see
Definition 2 in [3] and Section 8.2 in [2]), such that for any $b\in A$, and
any non-negative integer $m$,

$|\phi^{k}(a)|_{b}=\sum_{i,j}c_{i,j}m^{(k)}_{i,j},$

where $M^{k}=(m^{(k)}_{i,j})_{1\leq i,j\leq d}$ and $c_{i,j}$ are real numbers
independent from $k$. Moreover, let $\\{v_{1},v_{2},\cdots,v_{r}\\}$ be the
set of distinct eigenvalues of $M$, then $\alpha\geq|v_{i}|$ for any $i$. Let
$J$ be the Jordan form of $M$, then, there are some matrix $S$ such that for
any $k$, $M^{k}=S^{-1}J^{k}S$. Thus, for any pair of $1\leq i,j\leq d$, there
exist $r$ polynomials $p_{i,j,1},p_{i,j,2},\cdots,p_{i,j,r}$, such that

$m^{(k)}_{i,j}=\sum_{t=1}^{r}p_{i,j,r}(k)v_{t}^{k}.$

Consequently, for any $b\in A$, there exist $r$ polynomials
$p_{b,1},p_{b,2},\cdots,p_{b,r}$, such that

$|\phi^{k}(a)|_{b}=\sum_{t=1}^{r}p_{b,r}(k)v_{t}^{k}.$

Thus, there exists a $\beta\in\mathbb{R}$ such that $|\phi^{kT}(a)|_{b}\sim
G^{\prime}{kT}^{m}\sum_{i=1}^{s}\beta_{i}^{kT}$ and that $|\beta_{i}|=\beta$
for all $i$. For the uniqueness of $\beta_{i}$ in the case that
$\beta=\alpha$, see Remark 1 in [3].

###### Corollary 3

For any morphic sequence $(a_{n})_{n\in\mathbb{N}}$ over the alphabet $A^{*}$,
there exists an increasing sequence of integers $0\leq N_{1}\leq
N_{2}\leq\cdots\leq N_{k}\leq\cdots$, two real numbers $\alpha\geq 1$, $G>0$
and two non-negative integers $l$ and $T$ such that for any integer $k$,
$N_{k}\sim G(Tk)^{l}\alpha^{Tk}$.
Moreover, for any $a\in A$, there exist real numbers $\beta\leq\alpha$,
$G^{\prime}>0$, a non-negative integer $m$ and finitely many complex numbers
$\beta_{1},\beta_{2},\cdots,\beta_{s}$ such that $|\beta_{i}|=\beta$ for all
$i$ and that $|a[0,N_{k}]|_{a}\sim
G^{\prime}(Tk)^{m}\sum_{i=1}^{s}\beta_{i}^{Tk}.$
Moreover, if $\beta=\alpha$, then there exists a unique real number
$\beta_{1}=\beta$.

###### Proof

If $(a_{n})_{n\in\mathbb{N}}$ is morphic, from the definition, there exists an
alphabet $B$, a letter $b\in B$, a word $w\in B^{*}$, a non-erasing morphism
$\phi:B^{*}\to B^{*}$ and a coding function $\psi:B\to A$, such that
$\phi(b)=bw$ and
$(a_{n})_{n\in\mathbb{N}}=\lim_{i\to\infty}\psi(\phi^{i}(b))$. For any
positive integer $k$, let $N_{k}=|\phi^{k}(b)|$, then the first part is a
direct consequence of the first part of Proposition 2. For the second part, it
is enough to note that for any $a\in A$ there exist $b_{1},b_{2},\cdots
b_{t}\in B$ such that for any $k\geq 1$,

$|a[0,N_{k}]|_{a}=\sum_{i=1}^{t}|\psi(\phi^{i}(b))|_{b_{i}}.$

Then it follows the second part of Proposition 2.

######  Proof (Proof of Theorem 1)

With the same notation as previous, let $0\leq N_{1}\leq N_{2}\leq\cdots\leq
N_{k}\leq\cdots$ be defined as in Corollary 3. It is known that,

$N_{k}\sim G(Tk)^{l}\alpha^{Tk},$

and that for any $a$ in the sequence,

$|a[0,N_{k}]|_{a}\sim G^{\prime}(Tk)^{m}\sum_{i=1}^{s}\beta_{i}^{Tk},$

where $|\beta_{1}|=|\beta_{2}|=\cdots=|\beta_{s}|=\beta\leq\alpha$.

If $\beta<\alpha$, then there exists $c^{\prime}<0$, such that

$|a[0,N_{k}]|_{a}=O(N_{k}^{c^{\prime}})\nsim
C\frac{N_{k}}{(\log(N_{k}))^{\gamma}}.$

If $\beta=\alpha=1$, then, from Corollary 3, $|a[0,N_{k}]|_{a}\sim
G^{\prime}(Tk)^{m}$ and $N_{k}\sim G^{\prime}(Tk)^{l}$. In this case

$G^{\prime}(Tk)^{m}\nsim C\frac{G(Tk)^{l}}{(\log(G(Tk)^{l}))^{\gamma}},$

for any $C$, $m$ and $l$.

If $\beta=\alpha>1$, then, from Corollary 3, $|a[0,N_{k}]|_{a}\sim
G^{\prime}(Tk)^{m}(\alpha)^{Tk}$ and $N_{k}\sim
G^{\prime}(Tk)^{l}(\alpha)^{Tk}$.

$(\log{N_{k}})^{\gamma}\sim(\log{GT^{l}}+l\log{k}+kT\log{\alpha})^{\gamma}\sim
C(k)^{\gamma},$

for some constant $C$. However, since $0<\gamma<1$,

$C\frac{N_{k}}{(\log{N_{k}})^{\gamma}}\sim
C^{\prime}(k)^{l-\gamma}\alpha^{kT}\nsim G^{\prime}(kT)^{m}\alpha^{kT},$

for any integer $m$.

###### Proposition 4

[[10]] For any non-negative integer $N$, let $B(N)$ be the number of integers
$n$ such that $0\leq n\leq N$ and $s_{2}(n)=1$. Then, there exists a constant
K (known as Landau-Ramanujan constant), such that

$B(N)\sim K\frac{N}{\sqrt{\log(N)}}.$

###### Theorem 5

The sequence $(s_{2}(n))_{n\in\mathbb{N}}$ is not morphic.

###### Proof

It is a direct consequence if Theorem 1 and Proposition 4.

###### Theorem 6

Let $(s^{\prime}_{2}(n))_{n\in\mathbb{N}}$ be a $0,1$ sequence such that, for
any natural number $n$, $s^{\prime}_{2}(1)=1$ if and only if $n$ is a sum of
two non-zero squares. Then $(s^{\prime}_{2}(n))_{n\in\mathbb{N}}$ is not
morphic.

###### Proof

Similarly for any natural number $N$, define $B^{\prime}(N)$ to be the number
of integers $n$ such that $o\leq n\leq N$ ans $s^{\prime}_{2}(n)=1$.
Obviously,

$|B(N)-B^{\prime}(N)|\leq\sqrt{N}=o(K\frac{N}{\log(N)}),$

with the same notation in Proposition 4. Thus,

$B^{\prime}(N)\sim K\frac{N}{\sqrt{\log(N)}},$

and on can conclude using Theorem 1.

##  4 Discussion

The key technique of this proof is base on the estimation of $B(N)$, which is
obtained in using the fact that $(s_{2}(n))_{n\in\mathbb{N}}$ is
multiplicative. For any pair of integers $r,t$, let
$(s_{r,t}(n))_{n\in\mathbb{N}}$ be the sequence characterizing the integers
that are the sum of r numbers of $k$-power. The technique applied in [10] may
not useful to estimate the number of integers $n$ satisfying $n\leq N$ and
$s_{r,t}(n)=1$.

The author believes the following generalization of Theorem 1 is true:

###### Conjecture 7

Let $(a_{n})_{n\in\mathbb{N}}$ be a morphic sequence over the alphabet $A$. If
there exists $a\in A$, two positive numbers $0<\gamma<1$, $C>0$ and an
increasing sequence of integers $N_{1}<N_{2}<\cdots<N_{k}<\cdots$ such that

$|a[0,N_{k}]|_{a}\sim C\frac{N_{k}}{(\log(N_{k}))^{\gamma}},$

when $k$ is large, then $(a_{n})_{n\in\mathbb{N}}$ is not morphic.

## References

  * [1] Allouche, J.-P., Goldmakher, L.: Mock characters and the Kronecker symbol. Journal of Number Theory 192, 356–372 (2018)
  * [2] Allouche, J.-P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003)
  * [3] Bell, J.P.: Logarithmic frequency in morphic sequences. Journal de théorie des nombres de Bordeaux 20(2), 227–241 (2008)
  * [4] Cobham, A.: Uniform tag sequences. Math. Systems Theory 6, 164–192 (1972)
  * [5] Hu, Y.: Subword complexity and non-automaticity of certain completely multiplicative functions. Advances in Applied Mathematics 84, 73–81 (2017)
  * [6] Klurman, O., Kurlberg, P.: A note on multiplicative automatic sequences. Comptes Rendus. Mathématique 357(10), 752–755 (2019)
  * [7] Klurman, O., Kurlberg, P.: A note on multiplicative automatic sequences, II. Bulletin of the London Mathematical Society 52(1), 185–188 (2020)
  * [8] Konieczny, J.: On multiplicative automatic sequences. Bulletin of the London Mathematical Society 52(1), 175–184 (2020)
  * [9] Konieczny, J., Lemańczyk, M., Müllner, C.: Multiplicative automatic sequences. Mathematische Zeitschrift 300, 1297–1318 (2022)
  * [10] Landau, E.: Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindestzahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate. Archiv der Mathematik und Physik 13(3), 305–312 (1908)
  * [11] Li, S.: On completely multiplicative automatic sequences. Journal of Number Theory 213, 388–399 (2020)
  * [12] Minsky, M., Papert, S.: Unrecognizable sets of numbers. J. ACM 13(2), 281–286 (apr 1966)
  * [13] OEIS Foundation Inc.: The On-Line Encyclopedia of Integer Sequences (2024), published electronically at http://oeis.org
  * [14] Ritchie, R.W.: Finite automata and the set of squares. J. ACM 10(4), 528–531 (oct 1963)
  * [15] Tahay, P.A.: Characteristic sequences of the sets of sums of squares as columns of cellular automata. In: Frid, A., Mercaş, R. (eds.) Combinatorics on Words. pp. 288–300. Springer Nature Switzerland, Cham (2023)


# Logical properties of random graphs from small addable classes††thanks: The
research reported here was carried out during a visit by the second author to
the University of Cambridge in 2011, supported by the ESF Resaearch Networking
Programme GAMES. Eryk Kopczyński was also partially supported by the Polish
National Science research grant DEC-2012/07/D/ST6/02435.

Anuj Dawar, Eryk Kopczyñski

###### Abstract

We establish zero-one laws and convergence laws for monadic second-order logic
(MSO) (and, a fortiori, first-order logic) on a number of interesting graph
classes. In particular, we show that MSO obeys a zero-one law on the class of
connected planar graphs, the class of connected graphs of tree-width at most
$k$ and the class of connected graphs excluding the $k$-clique as a minor. In
each of these cases, dropping the connectivity requirement leads to a class
where the zero-one law fails but a convergence law for MSO still holds.

##  1 Introduction

The zero-one law for first-order logic [GKLT69, Fag76] established that every
first-order sentence $\phi$, when evaluated over a random $n$-element finite
structure, has a probability of being true that converges to either $0$ or $1$
as $n$ goes to infinity. This prompted much further investigation into the
asymptotic behaviour of classes of structures definable in logic. Zero-one
laws have been established for fragments of second-order logic [KV90];
extensions of first-order logic such as the infinitary logic
$L^{\omega}_{\infty\omega}$ [KV92] which subsumes various fixed-point logics;
and logics with generalized quantifiers [DG10], among many others.

Another widely studied extension of first-order logic is _monadic second-order
logic_ (MSO). This does not have a zero-one law but its asymptotic behaviour
has been studied on restricted classes of structures. For many interesting
classes it does admit a zero-one law, such as on free labelled trees [McC02].
On rooted labelled trees, MSO does not have a zero-one law, but still admits a
convergence law [McC02]. This means that the probability of any given sentence
$\phi$ being true in an $n$-element structure does converge to a limit, though
that limit is not necessarily $0$ or $1$. Zero-one and convergence laws for
MSO on a number of other classes are shown in [Com89].

In this paper, we are concerned with the asymptotic behaviour of first-order
logic (FO) and MSO on restricted classes of finite structures, and more
specifically, restricted classes of graphs. We look particularly at _tame_
classes of graphs in the sense of [Daw07]. These include planar graphs, graphs
of bounded treewidth and some other proper minor-closed classes. A flavour of
our results is given by the following examples. There is a constant $c\leq
0.036747$ such that the asymptotic probability of any MSO sentence $\phi$ on
the class of planar graphs converges to a real number in the range
$[0,c)\cup(1-c,1]$. On the class of _connected_ , planar graphs, MSO admits a
zero-one law. These results can be strengthened (modulo changing the constant
$c$) from planar graphs to other minor-closed classes of graphs that are
_smooth_ and _addable_ , which we define formally later. Here we note that
examples of smooth, addable, minor-closed graph classes include not just the
planar graphs but also the class of graphs of treewidth at most $k$, for any
$k$.

Technically, we rely on the combinatorial results on random planar graphs
proved in [MSW05] and the extensions to minor-closed classes established in
[McD09]. We combine these with logical techniques from [Com89] and [McC02].

Since the first submission, it has come to our attention that some of the
results reported here have also been obtained independently in [HMNT18].

##  2 Graph Classes

Let $R_{n}$ denote a random graph drawn from the uniform distribution on
graphs on the vertex set $[n]=\\{1,\ldots,n\\}$. Equivalently, $R_{n}$ is
obtained by putting, for each $i,j$ with $1\leq i<j\leq n$ an edge between $i$
and $j$ with probability $1/2$. If ${\mathcal{C}}$ is a class of graphs closed
under isomorphisms, we write ${\mathcal{C}}_{n}$ for the graphs in
${\mathcal{C}}$ on the vertex set $[n]$ and $R_{n}({\mathcal{C}})$ to denote
the random graph drawn from the uniform distribution on ${\mathcal{C}}_{n}$.
Unlike with $R_{n}$, it is not immediately clear how to effectively sample
from this distribution. When ${\mathcal{C}}$ is the class of planar graphs, a
first partially successful attempt was in [DVW96], using a Markov chain whose
only stable distribution is the uniform distribution on ${\mathcal{C}}_{n}$.
However, this is not quite practical as the mixing rate of this Markov chain
is unknown. Nevertheless, this formulation did enable experimental validation
of some conjectures about random planar graphs. Finally, in [BGK07], it is
shown that there is a polynomial-time algorithm that can generate a random
planar graph on $[n]$.

An excellent analysis of random planar graphs, resolving some conjectures of
[DVW96] was given in [MSW05]. Some of this analysis was predicated on a
conjecture, termed the “isolated vertices conjecture” to the effect that the
number of isolated vertices in a random planar graph on $[n]$ tends to a limit
as $n$ increases. This conjecture was proved in [GN05] and later shown [McD09]
to be an instance of the _smoothness_ of _addable_ minor-closed classes. Much
of the analysis of random planar graphs in [MSW05] can be extended to other
graph classes that are smooth, addable and _small_ [MSW06]. We begin by
defining these central notions.

###### Definition 2.1

Say that a graph class ${\mathcal{C}}$ is _decomposable_ if
$G\in{\mathcal{C}}$ if, and only if, every connected component of $G$ is in
${\mathcal{C}}$.

Equivalently, ${\mathcal{C}}$ is decomposable if, and only if, ${\mathcal{C}}$
is both closed under disjoint unions and closed under taking connected
components.

###### Definition 2.2

Say that graph class ${\mathcal{C}}$ is _bridge-addable_ if, for every
$G\in{\mathcal{C}}$, if $u$ and $v$ are vertices in distinct connected
components of $G$, then the graph obtained by adding the edge $\\{u,v\\}$ to
$G$ is also in ${\mathcal{C}}$.

###### Definition 2.3

A graph class ${\mathcal{C}}$ is _addable_ if it is both decomposable and
bridge-addable.

Note that the class of planar graphs is clearly addable. As noted in [MSW06],
the following classes of graphs are all addable: forests; the class of graphs
of treewidth at most $k$; the class of graphs with no cycle of length greater
than $k$; the class of graphs that exclude $K_{k}$ as a minor. On the other
hand, the class of graphs embeddable in a torus is not addable. It is bridge-
addable but not decomposable since it contains $K_{5}$ but not the graph that
is the disjoint union of two copies of $K_{5}$. In general, the class of
graphs of genus at most $k$ for positive $k$ is not addable.

We write ${Q_{n}}({\mathcal{C}})$ to denote the number of graphs in
${\mathcal{C}}_{n}$ (i.e. graphs in ${\mathcal{C}}$ on the vertex set $[n]$).

###### Definition 2.4

A graph class ${\mathcal{C}}$ is _small_ if ${Q_{n}}({\mathcal{C}})\leq
d^{n}n!$ for some $d\in{\mathbb{R}}$.

With any class ${\mathcal{C}}$, we can associate a _growth constant_
$\gamma_{{\mathcal{C}}}$ defined by
$\gamma_{{\mathcal{C}}}=\limsup_{n\rightarrow\infty}({Q_{n}}({\mathcal{C}})/n!)^{1/n}$.
Then, ${\mathcal{C}}$ is small just in case $\gamma_{{\mathcal{C}}}$ is
finite.

###### Definition 2.5

[MSW06] A graph class ${\mathcal{C}}$ is _smooth_ if
$\frac{{Q_{n}}}{n{Q_{n-1}}}$ tends to a finite limit as $n\rightarrow\infty$.

It is known (see [MSW06]) that if ${\mathcal{C}}$ is smooth, then the limit of
$\frac{{Q_{n}}}{n{Q_{n-1}}}$ is the growth constant $\gamma_{{\mathcal{C}}}$.
Thus, every smooth class is small. However, there are small graph classes that
are not smooth. When ${\mathcal{C}}$ is the class of forests,
$\gamma_{{\mathcal{C}}}=e$. We can now state the two results on smoothness
that we need.

###### Theorem 2.6

[GN05] The class of planar graphs is smooth, and the growth constant is
$\gamma\approx 27.22679$ and is given by an explicit analytic expression.

###### Theorem 2.7

[McD09] Each addable proper minor-closed class of graphs is smooth.

##  3 Logics

We assume the reader is familiar with the syntax and semantics of first-order
logic (FO) and monadic second-order logic (MSO) interpreted on finite
structures, as defined, for instance in [Lib04]. We give a brief review of
definitions, especially where our notation deviates from the standard.

###  3.1 Basics

We assume we have two disjoint countable sets of symbols ${\rm{Var}}^{1}$ (the
first-order variables) and ${\rm{Var}}^{2}$ (the second-order variables).
Given a graph $G=(V,E)$, a _valuation_ $\sigma$ on $G$ is a pair
$(\sigma^{1},\sigma^{2})$ of _partial_ functions
$\sigma^{1}:{\rm{Var}}^{1}\rightharpoonup V$ and
$\sigma^{2}:{\rm{Var}}^{2}\rightharpoonup\mathscr{P}(V)$. For
$x\in{\rm{Var}}^{1}\cup{\rm{Var}}^{2}$, we use $\sigma(x)$ to denote
$\sigma^{1}(x)$ or $\sigma^{2}(x)$ as appropriate.

A _structure_ is a pair ${\mathfrak{G}}=(G,\sigma)$ where $G$ is a graph and
$\sigma$ is a valuation on $G$. If ${\mathfrak{G}}=(G=(V,E),\sigma)$ is a
structure, we sometimes write $G({\mathfrak{G}})$, $V({\mathfrak{G}})$,
$E({\mathfrak{G}})$, $\sigma({\mathfrak{G}})$, $x({\mathfrak{G}})$ to denote
$G,V,E,\sigma,\sigma(x)$, respectively. Moreover, we write
${\rm{Var}}^{1}({\mathfrak{G}})$ and ${\rm{Var}}^{2}({\mathfrak{G}})$ to
denote the subsets of ${\rm{Var}}^{1}$ and ${\rm{Var}}^{2}$ respectively on
which $\sigma^{1}({\mathfrak{G}})$ and $\sigma^{2}({\mathfrak{G}})$ are
defined. For even greater brevity, when referring to a structure
${\mathfrak{G}}_{1}$, we may write $G_{1},V_{1}$, etc. for
$G({\mathfrak{G}}_{1})$, $V({\mathfrak{G}}_{1})$, etc. when no ambiguity
arises. We write $\sigma[v/x]$ to denote the valuation that agrees with
$\sigma$ at all values other than $x$ and that maps $x$ to $v$. We also write
${\mathfrak{G}}[v/x]$ to denote
$(G({\mathfrak{G}}),\sigma({\mathfrak{G}})[v/x])$ and ${\mathfrak{G}}[/x]$ to
denote the structure $(G({\mathfrak{G}}),\sigma^{\prime}({\mathfrak{G}}))$
where the valuation $\sigma^{\prime}$ is the same as $\sigma$ except that it
is undefined at $x$.

Note that, by including the interpretation of variables in our definition of
structure, we can uniformly talk of graphs, coloured graphs and graphs with
distinguished constants as structures, all over a fixed vocabulary.

The formulas of MSO are built-up as usual according to the following grammar,
where $\phi_{1}$ and $\phi_{2}$ are formulas, $x,y\in{\rm{Var}}^{1}$ and
$X,Y\in{\rm{Var}}^{2}$.

$\phi\ ::=\ x\in X\mid
E(x,y)\mid\phi_{1}\wedge\phi_{2}\mid\phi_{1}\vee\phi_{2}\mid\neg\phi_{1}\mid\forall
x\phi\mid\exists x\phi\mid\forall_{2}X\phi\mid\exists_{2}X\phi$

The formulas of first-order logic are those that involve no occurrence of a
variable from ${\rm{Var}}^{2}$.

The definition of satisfaction ${\mathfrak{G}}\models\phi$ is standard. We
define the _quantifier rank_ of a formula $\phi$, denoted ${\rm qr}(\phi)$, to
be the maximum depth of nesting of quantifiers in $\phi$ counting both first-
and second-order quantifiers (as in [Lib04, Definition 7.4]).

###  3.2 Ehrenfeucht-Fraïssé games

We write ${\mathfrak{G}}_{1}\equiv_{m}{\mathfrak{G}}_{2}$ to denote that the
two structures ${\mathfrak{G}}_{1}$ and ${\mathfrak{G}}_{2}$ cannot be
distinguished by any formula with quantifier rank at most $m$. Formally, this
is defined by induction on $m$ as follows. We say that
${\mathfrak{G}}_{1}\equiv_{0}{\mathfrak{G}}_{2}$ if, for any quantifier-free
formula $\phi$ such that $\sigma_{1}$ and $\sigma_{2}$ are defined on all the
free variables of $\phi$, we have that ${\mathfrak{G}}_{1}\models\phi$ if, and
only if, ${\mathfrak{G}}_{2}\models\phi$. Inductively, we say that
${\mathfrak{G}}_{1}\equiv_{m+1}{\mathfrak{G}}_{2}$ if all the following
conditions are satisfied.

  * •

For $x\in{\rm{Var}}^{1}$, $\forall v_{1}\in V_{1}\exists v_{2}\in
V_{2}{\mathfrak{G}}_{1}[v_{1}/x]\equiv_{m}{\mathfrak{G}}_{2}[v_{2}/x]$.

  * •

For $x\in{\rm{Var}}^{1}$, $\forall v_{2}\in V_{2}\exists v_{1}\in
V_{1}{\mathfrak{G}}_{1}[v_{1}/x]\equiv_{m}{\mathfrak{G}}_{2}[v_{2}/x]$.

  * •

For $X\in{\rm{Var}}^{2}$, $\forall U_{1}\subseteq V_{1}\exists U_{2}\subseteq
V_{2}{\mathfrak{G}}_{1}[U_{1}/X]\equiv_{m}{\mathfrak{G}}_{2}[U_{2}/X]$.

  * •

For $X\in{\rm{Var}}^{2}$, $\forall U_{2}\subseteq V_{2}\exists U_{1}\subseteq
V_{1}{\mathfrak{G}}_{1}[U_{1}/X]\equiv_{m}{\mathfrak{G}}_{2}[U_{2}/X]$.

As usual, this definition ${\mathfrak{G}}_{1}\equiv_{m}{\mathfrak{G}}_{2}$ can
be understood as a game between two players conventionally called Spoiler and
Duplicator (known as the _$m$ -round Ehrenfeucht-Fraïssé game_). The game is
played on a “board” consisting of two structures ${\mathfrak{G}}_{1}$ and
${\mathfrak{G}}_{2}$. For $m=0$, Duplicator wins iff
${\mathfrak{G}}_{1}\equiv_{0}{\mathfrak{G}}_{2}$. Otherwise, Spoiler chooses
either a variable $x\in{\rm{Var}}^{1}$ and a vertex $v_{i}$ in one of the
graphs $G_{i}$ or a variable $X\in{\rm{Var}}^{2}$ and a set of vertices
$U_{i}\subseteq V_{i}$ in the graph $G_{i}$. In the first case, Duplicator
responds by choosing an element $v_{3-i}\in G_{3-i}$ and the play then
proceeds for $m-1$ rounds starting with the board
${\mathfrak{G}}_{1}[v_{1}/x]$ and ${\mathfrak{G}}_{2}[v_{2}/x]$. In the second
case, Duplicator responds by choosing a set $U_{3-i}\subseteq V_{3-i}$ and
again the play then proceeds for $m-1$ rounds starting with the board
${\mathfrak{G}}_{1}[U_{1}/X]$ and ${\mathfrak{G}}_{2}[U_{2}/X]$. Then, it is
clear that Duplicator has a strategy for winning the $m$ round game on the
board ${\mathfrak{G}}_{1}$ and ${\mathfrak{G}}_{2}$ just in case
${\mathfrak{G}}_{1}\equiv_{m}{\mathfrak{G}}_{2}$. The connection with MSO
comes from the following standard theorem (see [Lib04, Theorem 7.7])

###### Theorem 3.1

The following conditions are equivalent:

  * •

${\mathfrak{G}}_{1}\equiv_{m}{\mathfrak{G}}_{2}$

  * •

${\mathfrak{G}}_{1}$ and ${\mathfrak{G}}_{2}$ satisfy exactly the same MSO
formulas of quantifier rank at most $m$.

Finally, we note that, if we have only a fixed finite set of variables, then
the equivalence relation $\equiv_{m}$ is of finite index for each $m$. That
is, fix a finite set $\Xi\subseteq{\rm{Var}}$ and let $\mathcal{S}[\Xi]$
denote the class of structures ${\mathfrak{G}}$ such that
${\rm{Var}}^{1}({\mathfrak{G}}),{\rm{Var}}^{2}({\mathfrak{G}})\subseteq\Xi$.

###### Proposition 3.2

The relation $\equiv_{m}$ restricted to $\mathcal{S}[\Xi]$ has finite index.

The proof is a proof by induction that there are, up to equivalence, only
finitely many formulas of MSO of quantifier rank $m$ with free variables among
$\Xi$ (see [Lib04, Prop. 7.5]). We write $t_{m}(\Xi)$ to denote the index of
$\equiv_{m}$ restricted to $\mathcal{S}[\Xi]$. Note that the value of
$t_{m}(\Xi)$ is completely determined by the number of elements in
$\Xi\cap{\rm{Var}}^{1}$ and $\Xi\cap{\rm{Var}}^{2}$.

##  4 Adding graphs

For structures ${\mathfrak{G}}_{1}$ and ${\mathfrak{G}}_{2}$, the disjoint
union ${\mathfrak{G}}_{1}\oplus{\mathfrak{G}}_{2}$ is defined if
${\rm{Var}}^{1}_{1}\cap{\rm{Var}}^{1}_{2}=\emptyset$. In this case, the set of
vertices of ${\mathfrak{G}}_{3}={\mathfrak{G}}_{1}\oplus{\mathfrak{G}}_{2}$ is
the disjoint union of $V_{1}$ and $V_{2}$, $E_{3}=E_{1}\cup E_{2}$,
$\sigma^{1}_{3}(x)=\sigma_{i}^{1}(x)$ for $i\in\\{1,2\\}$ whenever
$x\in{\rm{Var}}^{1}_{i}$ and
$\sigma^{2}_{3}(X)=\sigma_{1}^{2}(X)\cup\sigma_{2}^{2}(X)$.

It is well-known that the equivalence relation $\equiv_{m}$ is a congruence
with respect to the disjoint union of structures. Moreover, for every $m$ and
finite set $\Xi\subseteq{\rm{Var}}^{1}\cup{\rm{Var}}^{2}$ there is a threshold
$r_{m}(\Xi)$ such that for any $p,q>r_{m}(\Xi)$, the disjoint union of $p$
copies of a structure is $\equiv_{m}$-equivalent to the disjoint union of $q$
copies. We formally state this for later use.

###### Lemma 4.1

Fix a positive integer $m$ and a finite set
$\Xi\subseteq{\rm{Var}}^{1}\cup{\rm{Var}}^{2}$. There is a positive integer
$r_{m}(\Xi)$ such that if $\\{{\mathfrak{G}}_{i}\mid i\in I\\}$ is a
collection of structures such that
${\mathfrak{G}}_{i}\equiv{\mathfrak{G}}_{j}$ for all $i,j\in I$ and
$P,Q\subseteq I$ are sets such that either $|P|=|Q|$ or $|P|,|Q|\geq
r_{m}(\Xi)$ then

$\bigoplus_{i\in P}{\mathfrak{G}}_{i}\equiv_{m}\bigoplus_{j\in
Q}{\mathfrak{G}}_{j}.$

Indeed, similar facts can be established for many operations other than
disjoint union (see, for example [Mak04]). Here, we are also interested in a
particular operation of taking the disjoint union of two structures while
adding an edge between distinguished vertices (as in the definition of bridge
addable graphs: Definition 2.2). We give the formal definition below and prove
the properties we need.

We say that a structure ${\mathfrak{G}}$ is _rooted_ if
${\rm{Root}}\in{\rm{Var}}^{1}({\mathfrak{G}})$.

Let ${\mathfrak{G}}_{1}$ and ${\mathfrak{G}}_{2}$ be two rooted structures
such that ${\rm{Var}}^{1}_{1}\cap{\rm{Var}}^{1}_{2}=\\{{\rm{Root}}\\}$ and
$V_{1}\cap V_{2}=\emptyset$. We write ${\mathfrak{G}}_{1}+{\mathfrak{G}}_{2}$
to denote the structure ${\mathfrak{G}}$ such that:

  * •

$V=V_{1}\cup V_{2}$, $E=E_{1}\cup
E_{2}\cup\\{\sigma_{1}({\rm{Root}}),\sigma_{2}({\rm{Root}})\\}$

  * •

$\sigma(X)=\sigma_{1}(X)\cup\sigma_{2}(X)$ for
$X\in{\rm{Var}}^{2}_{1}\cap{\rm{Var}}^{2}_{2}$

  * •

$\sigma(X)=\sigma_{i}(X)$ for $X\in{\rm{Var}}^{2}_{i}-{\rm{Var}}^{2}_{3-i}$

  * •

$\sigma({\rm{Root}})=\sigma_{1}({\rm{Root}})$

  * •

$\sigma(x)=\sigma_{i}(x)$ for $x\in{\rm{Var}}^{1}_{i}$ and $x\neq{\rm{Root}}$

That is to say that ${\mathfrak{G}}_{1}+{\mathfrak{G}}_{2}$ is obtained by
taking the disjoint union of the structures ${\mathfrak{G}}_{1}$ and
${\mathfrak{G}}_{2}$ seen as coloured graphs, putting an edge between the two
roots, and making the root of ${\mathfrak{G}}_{1}$ the root of the combined
structure. This asymmetry in the choice of root means that, in general
${\mathfrak{G}}_{1}+{\mathfrak{G}}_{2}\neq{\mathfrak{G}}_{2}+{\mathfrak{G}}_{1}$.
However, it is still the case that
$({\mathfrak{G}}_{1}+{\mathfrak{G}}_{2})+{\mathfrak{G}}_{3}=({\mathfrak{G}}_{1}+{\mathfrak{G}}_{3})+{\mathfrak{G}}_{2}$.

A simple argument using Ehrenfeucht-Fraïssé games establishes the following
proposition.

###### Proposition 4.2

If ${\mathfrak{G}}_{1}\equiv_{m}{\mathfrak{G}}_{2}$, then
${\mathfrak{G}}_{0}+{\mathfrak{G}}_{1}\equiv_{m}{\mathfrak{G}}_{0}+{\mathfrak{G}}_{2}$.

Proof Suppose Duplicator has a winning strategy in the $m$-move Ehrenfeucht-
Fraïssé game played on ${\mathfrak{G}}_{1}$ and ${\mathfrak{G}}_{2}$. We show
that she also has a winning strategy in the $m$-move game on
${\mathfrak{G}}_{0}+{\mathfrak{G}}_{1}$ and
${\mathfrak{G}}_{0}+{\mathfrak{G}}_{2}$. The strategy is described as follows.

  * •

if Spoiler chooses $w\in V_{0}$, then Duplicator responds with the same $w$;

  * •

if Spoiler chooses $w\in V_{i}$ for $i\in\\{1,2\\}$, then Duplicator responds
with $w^{\prime}\in V_{3-i}$ given by her winning strategy in the game on
${\mathfrak{G}}_{1}$ and ${\mathfrak{G}}_{2}$; and

  * •

if Spoiler chooses $W\subseteq V_{0}\cup V_{i}$ for $i\in\\{1,2\\}$, then
Duplicator responds with $(W\cap V_{0})\cup W_{2}$, where $W_{2}$ is her
response to $W\cap V_{i}$ in the game on ${\mathfrak{G}}_{1}$ and
${\mathfrak{G}}_{2}$.

It is easy to show that this does indeed describe a winning strategy.

If ${\mathfrak{G}}_{2}$ is a structure with
${\rm{Var}}^{1}_{2}=\\{{\rm{Root}}\\}$ and $c$ is a positive integer, we write
${\mathfrak{G}}_{1}+c{\mathfrak{G}}_{2}$ to denote the structure obtained by
adding ${\mathfrak{G}}_{2}$ to ${\mathfrak{G}}_{1}$ $c$ times. More formally,
this is defined by induction on $c$:

  * •

${\mathfrak{G}}_{1}+0{\mathfrak{G}}_{2}={\mathfrak{G}}_{1}$,

  * •

${\mathfrak{G}}_{1}+(c+1){\mathfrak{G}}_{2}=({\mathfrak{G}}_{1}+c{\mathfrak{G}}_{2})+{\mathfrak{G}}_{2}$

Analogously to Lemma 4.1, we have the following proposition.

###### Proposition 4.3

Let $\Xi\subseteq{\rm{Var}}$ be a finite set. For each $m$, there is number
$q_{m}(\Xi)$ such that for any ${\mathfrak{G}}\in\mathcal{S}[\Xi]$ and any
structure ${\mathfrak{G}}_{0}$ we have

${\mathfrak{G}}_{0}+p{\mathfrak{G}}\equiv_{m}{\mathfrak{G}}_{0}+q{\mathfrak{G}}$

whenever $p,q\geq q_{m}(\Xi)$.

Proof We define the value of $q_{m}(\Xi)$ by induction on $m$, simultaneously
for all finite sets $\Xi\subseteq{\rm{Var}}$.

  * •

$q_{0}(\Xi)=0$ for all $\Xi$; and

  * •

$q_{m+1}(\Xi)=\max(q_{m}(\Xi\cup\\{x\\})+1,\ t_{m}(\Xi\cup\\{X\\})\cdot
q_{m}(\Xi\cup\\{X\\})+m)$,

where $x\in{\rm{Var}}^{1},\ X\in{\rm{Var}}^{2}$ are any variables not in
$\Xi$. Recall that $t_{m}(\Xi)$ denotes the index of the relation $\equiv_{m}$
in $\mathcal{S}[\Xi]$.

Now, we argue by induction on $m$ that if $p,q\geq q_{m}(\Xi)$ then
${\mathfrak{G}}_{0}+p{\mathfrak{G}}\equiv_{m}{\mathfrak{G}}_{0}+q{\mathfrak{G}}$.
In the following, we use the sets $[p]$ and $[q]$ to index the copies of
${\mathfrak{G}}$. Thus, we may refer to the graph $G_{i}$ for $i\in[p]$. The
base case, $m=0$ is immediate. Suppose now that the claim is true for some $m$
and all finite $\Xi$, and let
${\mathfrak{G}}_{A}={\mathfrak{G}}_{0}+p{\mathfrak{G}}$ and
${\mathfrak{G}}_{B}={\mathfrak{G}}_{0}+q{\mathfrak{G}}$ for some $p,q\geq
q_{m+1}(\Xi)$. We consider a number of cases corresponding to different moves
that Spoiler might make in the Ehrenfeucht-Fraïssé game.

  * •

Suppose $x\in{\rm{Var}}^{1}$ and $v\in V_{0}$. Then,

$\begin{array}[]{lcl}({\mathfrak{G}}_{0}+p{\mathfrak{G}})[v/x]&=&{\mathfrak{G}}_{0}[v/x]+p{\mathfrak{G}}\\\
&\equiv_{m}&{\mathfrak{G}}_{0}[v/x]+q{\mathfrak{G}}\\\
&=&({\mathfrak{G}}_{0}+q{\mathfrak{G}})[v/x],\end{array}$

where the central $\equiv_{m}$ is true by induction hypothesis, since $p,q\geq
q_{m+1}(\Xi)>q_{m}(\Xi\cup\\{x\\})$.

  * •

Suppose $x\in{\rm{Var}}^{1}$ and $v\in V_{i}$ for $i\in[p]$. Then

$\begin{array}[]{lcl}({\mathfrak{G}}_{0}+p{\mathfrak{G}})[v/x]&\cong&({\mathfrak{G}}_{0}+{\mathfrak{G}})[v/x]+(p-1){\mathfrak{G}}\\\
&\equiv_{m}&({\mathfrak{G}}_{0}+{\mathfrak{G}})[v/x]+(q-1){\mathfrak{G}}\\\
&\cong&({\mathfrak{G}}_{0}+q{\mathfrak{G}})[v/x],\end{array}$

where the central $\equiv_{m}$ is again true by induction hypothesis, since
$p-1,q-1\geq q_{m}(\Xi\cup\\{x\\})$. The situation where $v\in V_{i}$ for
$i\in[q]$ is entirely symmetric.

  * •

Suppose now that $X\in{\rm{Var}}^{2}$ and $U\subseteq V_{A}$. We partition
$[p]$ into sets $P_{1},\ldots,P_{t}$ where $t\leq t_{m}(\Xi\cup\\{X\\})$ such
that $i$ and $j$ are in the same part if, and only if,
${\mathfrak{G}}_{i}[U\cap V_{i}/X]\equiv_{m}{\mathfrak{G}}_{j}[U\cap
V_{j}/X]$. Since $p,q\geq q_{m+1}(\Xi)\geq t_{m}(\Xi\cup\\{X\\})\cdot
q_{m}(\Xi\cup\\{X\\})$ we can partition $[q]$ into parts $Q_{1},\ldots,Q_{t}$
such that for all $k$, either $P_{k}$ and $Q_{k}$ have the same size, or they
both have more than $q_{m}(\Xi\cup\\{X\\})$ elements. For each $l$ choose an
$i_{l}\in P_{l}$ and define, for $j\in[q]$, $U^{\prime}_{j}$ to be $U\cap
V_{i_{l}}$ whenever $j\in Q_{l}$. Let
$U^{\prime}=\bigcup_{j\in[q]}U^{\prime}_{j}$. Then, by the induction
hypothesis and Proposition 4.2, it follows that
${\mathfrak{G}}_{A}[U/X]\equiv_{m}{\mathfrak{G}}_{B}[U/X]$. Again, the case
when $U\subseteq V_{B}$ is entirely symmetric.

###  4.1 Universal Connected Structure

There is a sentence of MSO (with quantifier rank 5) which is true in a
structure ${\mathfrak{G}}$ if, and only if, ${\mathfrak{G}}$ is connected. It
follows that if $m\geq 5$ then each $\equiv_{m}$ class of structures either
contains only connected structures or disconnected ones.

For the rest of this subsection, we fix a value $m$ with $m\geq 5$. Also, let
${\mathcal{C}}$ be a class of graphs closed under the operation $+$. Let
${\mathfrak{G}}_{1},\ldots,{\mathfrak{G}}_{t}$ (with $t<t_{m}(\emptyset)$) be
a set of representatives from ${\mathcal{C}}$ of all $\equiv_{m}$ classes of
connected graphs which have elements in ${\mathcal{C}}$. Let
${\mathfrak{G}}_{R}$ denote the rooted structure with one element, no edges,
and interpreting no variables other than Root. We define the _$m$ -universal
connected rooted graph in ${\mathcal{C}}$_ to be the structure
${\mathfrak{G}}_{U(m)}={\mathfrak{G}}_{R}+\sum_{1\leq i\leq
t}q_{k}(\emptyset){\mathfrak{G}}_{i}$. That is, ${\mathfrak{G}}_{U(m)}$ is
obtained by adding $q_{k}(\emptyset)$ copies of a representative of each
$\equiv_{m}$ class of graphs to ${\mathfrak{G}}_{R}$. Changing the order in
which these graphs are added does not change the isomorphism type of
${\mathfrak{G}}_{U(m)}$ and changing the choice of representatives
${\mathfrak{G}}_{1},\ldots,{\mathfrak{G}}_{t}$ does not affect the
$\equiv_{m}$ class of ${\mathfrak{G}}_{U(m)}$.

###### Definition 4.4

Say that a rooted structure ${\mathfrak{G}}$ _appears_ in a graph
${\mathfrak{G}}_{1}$ if there is an induced substructure ${\mathfrak{G}}_{2}$
of ${\mathfrak{G}}_{1}$ and a vertex $r\in V_{2}$ such that:

  * •

${\mathfrak{G}}$ is isomorphic to ${\mathfrak{G}}_{2}[r/{\rm{Root}}]$; and

  * •

there is only one edge between $V_{2}$ and $V_{1}\setminus V_{2}$ and this
edge is incident on $r$.

###### Proposition 4.5

If the universal structure ${\mathfrak{G}}_{U(m)}$ appears in a connected
graph ${\mathfrak{G}}$, then
${\mathfrak{G}}\equiv_{m}{\mathfrak{G}}_{U(m)}[/{\rm{Root}}]$.

Proof By the definition of appearance, there is a vertex $r$ in
${\mathfrak{G}}$ such that ${\mathfrak{G}}[r/{\rm{Root}}]$ is isomorphic to
${\mathfrak{G}}_{U(m)}+{\mathfrak{G}}^{\prime}$ for some
${\mathfrak{G}}^{\prime}$. Let $i$ be such that ${\mathfrak{G}}_{i}$ with
${\mathfrak{G}}_{i}\equiv_{m}{\mathfrak{G}}^{\prime}$ is the representative of
the $\equiv_{m}$ equivalence class of ${\mathfrak{G}}^{\prime}$ in the
definition of ${\mathfrak{G}}_{U(m)}$. Then, by Prop. 4.2,
${\mathfrak{G}}[r/{\rm{Root}}]\equiv_{m}{\mathfrak{G}}_{U(m)}+{\mathfrak{G}}_{i}$.
Since, ${\mathfrak{G}}_{U(m)}$ contains more than $q_{m}(\emptyset)$ copies of
${\mathfrak{G}}_{i}$, Prop, 4.3 gives us that
${\mathfrak{G}}_{U(m)}\equiv_{m}{\mathfrak{G}}_{U(m)}+{\mathfrak{G}}_{i}$ and
the result follows.

##  5 MSO zero-one law for random connected graphs

Let ${\mathcal{C}}$ be a class of graphs. Recall that ${\mathcal{C}}_{n}$ is
the class of graphs in ${\mathcal{C}}$ on the vertex set $[n]$ and
$R_{n}({\mathcal{C}})$ denotes the random graph drawn from the uniform
distribution on ${\mathcal{C}}_{n}$. The following is a direct consequence of
Theorem 1.1 in [CP16].

###### Theorem 5.1

Let ${\mathcal{C}}$ be a small addable class of graphs. Then
$R_{n}({\mathcal{C}})$ is connected with probability at least
$1/\sqrt{e}-o(1)$.

Indeed, Theorem 1.1 of [CP16] establishes this more generally for _bridge
addable_ classes. The bound $1/\sqrt{e}$ is tight in that this is the limiting
probability for connectedness among forests.

We also rely on the following result which is obtained as a consequence of
Theorem 5.1 in [MSW06].

###### Theorem 5.2

Let ${\mathcal{C}}$ be a small addable class of graphs, and ${\mathfrak{G}}$
be a rooted graph in ${\mathcal{C}}$. Then the probability that
${\mathfrak{G}}$ appears in $R_{n}({\mathcal{C}})$ tends to 1 as
$n\rightarrow\infty$.

In fact, Theorem 5.1 of [MSW06] establishes the stronger result that the
number of appearances of ${\mathfrak{G}}$ in $R_{n}({\mathcal{C}})$ grows
linearly with $n$ (more precisely, there is an $\alpha>0$ such that the
probability that ${\mathfrak{G}}$ appears $\alpha n$ times tends to 1).

Together, these enable us to establish the zero-one law for the class of
connected graphs in any small addable class ${\mathcal{C}}$. In the following
we write Conn for the class of _connected_ graphs.

###### Theorem 5.3

Let $\phi$ be a sentence of MSO, and ${\mathcal{C}}$ a small addable class of
graphs. Let $p_{n}$ denote the probability that
$R_{n}({\mathcal{C}}\cap{\rm{Conn}})$ satisfies $\phi$. Then
$\lim_{n\rightarrow\infty}p_{n}$ is defined and equal to either $0$ or $1$.

Proof Let $m$ be the quantifier rank of $\phi$. By Theorem 5.2 we know that
the probability that ${\mathfrak{G}}_{U(m)}$ appears in $R_{n}({\mathcal{C}})$
tends to 1. Moreover, since the probability that $R_{n}({\mathcal{C}})$ is
connected is non-zero (by Theorem 5.1) it follows that the probability that
${\mathfrak{G}}_{U(m)}$, the $m$-universal connected rooted graph in
${\mathcal{C}}$, appears in $R_{n}({\mathcal{C}}\cap{\rm{Conn}})$ also tends
to $1$. Thus, by Proposition 4.5, with probability tending to $1$, we have
$R_{n}({\mathcal{C}}\cap{\rm{Conn}})\equiv_{m}{\mathfrak{G}}_{U(m)}$. Hence,
if ${\mathfrak{G}}_{U(m)}\models\phi$, then $p_{n}$ tends to $1$, otherwise
$p_{n}$ tends to $0$.

As an immediate consequence, we have a zero-one law for MSO for a number of
interesting classes of graphs.

###### Corollary 5.4

MSO admits a zero-one law on each of the following classes of graphs.

  * •

The class of connected planar graphs.

  * •

For each $k$, the class of connected graphs of tree-width at most $k$.

  * •

For each $k>2$, the class of connected graphs excluding $K_{k}$ as a minor.

##  6 MSO limit law for random graphs

We are now ready to establish our general result on the existence of a limit
law (also known as a convergence law) for MSO on smooth addable classes of
graphs. Note that, while Theorem 5.3 was stated for small addable classes,
from now on we will restrict ourselves further to _smooth_ classes. Recall
that every smooth class is also small.

To establish the limit law we need two specific results from [MSW06]. The
first is a direct consequence of Theorem 6.4 in that paper.

###### Theorem 6.1

Let ${\mathcal{C}}$ be a smooth addable class of graphs. For any $\epsilon>0$
there exist a constant $g(\epsilon)$ such that, for sufficiently large values
of $n$, with probability at least $1-\epsilon$, $R_{n}({\mathcal{C}})$ has a
connected component which contains at least $n-g(\epsilon)$ vertices.

In general, we refer to the _giant component_ of $R_{n}({\mathcal{C}})$.

The second result we need is a consequence of Theorem 9.2 of [MSW06].

###### Theorem 6.2

Let ${\mathcal{C}}$ be a smooth addable class of graphs, $H$ be a connected
graph, and $k\in{\mathbb{N}}$. Then there is a number $p_{k}(H)$ such that the
probability that $R_{n}({\mathcal{C}})$ has exactly $k$ components isomorphic
to $H$ tends to $p_{k}(H)$. Moreover, these events are asymptotically
independent for non-isomorphic graphs $H$.

Actually, Theorem 9.2 of [MSW06] does not state that the events are
asymptotically independent, but it is easily seen to be the case. Indeed, what
is stated there is that the distribution of the number of components
isomorphic to $H$ tends to Poisson distribution as $n\rightarrow\infty$, with
parameter $\lambda=1/(\gamma({\mathcal{C}})^{|H|}|{\rm{Aut}}(H)|)$, where
$|{\rm{Aut}}(H)|$ is the number of automorphisms of $H$.

As an example, for large values of $n$, the random planar graph on $n$
vertices has on average $1/\gamma({\mathcal{C}})\approx 0.03673$ isolated
vertices, $1/2\gamma({\mathcal{C}})^{2}<0.0007$ pairs of vertices with an edge
between them (and no other edges incident on them), less than $0.00004$
isolated connected subgraphs with 3 vertices, and so on. Summing over all of
these, we can show that the random planar graph has $\lambda\approx 0.037439$
connected components other than the giant component on average. From the fact
that the distribution is Poisson we get that the probability that the graph is
not connected is $1-e^{-\lambda}\approx 0.036746$.

We are interested in the frequency of occurrence of connected components, not
just up to isomorphism, but up to $\equiv_{m}$ for suitable values of $m$.
Specifically, we are interested in whether the number of components from a
fixed $\equiv_{m}$ equivalence class is greater than the threshold
$r_{m}(\emptyset)$ from Lemma 4.1 and the exact number if it is not. In the
following result, we use Theorems 6.1 and 6.2 to show that the relevant
probabilities converge.

###### Theorem 6.3

Let ${\mathcal{C}}$ be a smooth addable class of graphs and
$m\in{\mathbb{N}}$. If ${\mathcal{A}}$ is an $\equiv_{m}$-equivalence class of
connected graphs then for each $k\leq r_{m}(\emptyset)$ there is a
$p_{k}({\mathcal{A}})\in{\mathbb{R}}$ such that the probability that
$R_{n}({\mathcal{C}})$ has exactly $k$ components from ${\mathcal{A}}$ tends
to $p_{k}({\mathcal{A}})$ as $n$ goes to infinity.

Proof Let $p_{n}$ denote the probability that $R_{n}({\mathcal{C}})$ contains
exactly $k$ components in ${\mathcal{A}}$. We show that for any $\epsilon>0$
there is a $p$ such that $|p_{n}-p|<\epsilon$ for large enough $n$. Thus, the
sequence $(p_{n})_{n\in{\mathbb{N}}}$ is a Cauchy sequence and so converges to
a limit.

Let $g=g(\epsilon/3)$ be the value given by Theorem 6.1 such that, for
sufficiently large $n$, with probability at least $1-\epsilon/3$,
$R_{n}({\mathcal{C}})$ has a connected component which contains at least $n-g$
vertices. Moreover, let $n_{0}\in{\mathbb{N}}$ be such that for all $n>n_{0}$,
this probability is indeed at least $1-\epsilon/3$.

By exactly the same argument as in the proof of Theorem 5.3, we can show that
the conditional probability, given that $R_{n}({\mathcal{C}})$ has a connected
component which contains at least $n-g$ vertices, that this giant component is
$\equiv_{m}$-equivalent to ${\mathfrak{G}}_{U(m)}$, the $m$-universal
connected rooted graph in ${\mathcal{C}}$, tends to $1$ as $n$ goes to
infinity. Thus, we can fix a value $n_{1}\in{\mathbb{N}}$ such that this
probability is at least $1-\epsilon/3$ for all $n>n_{1}$.

Let $H_{1},\ldots,H_{M}$ enumerate (up to isomorphism) all graphs in
${\mathcal{A}}$ with at most $g$ vertices. Let $K$ denote the collection of
all functions $f:[M]\rightarrow{\mathbb{N}}$ such that $\sum_{i\in[M]}f(i)=k$
and note that this is a finite set. Let $p=\sum_{f\in
K}\prod_{i\in[M]}p_{f(i)}(H_{i})$, where $p_{f(i)}(H_{i})$ is the limiting
probability, given by Theorem 6.2, that $R_{n}({\mathcal{C}})$ contains
exactly $f(i)$ components isomorphic to $H_{i}$. If $p^{\prime}_{n}$ denotes
the probability that $R_{n}({\mathcal{C}})$ contains exactly $k$ components
that are isomorphic to one of $H_{1},\ldots,H_{M}$, then clearly the sequence
$(p^{\prime}_{n})_{n\in{\mathbb{N}}}$ tends to the limit $p$. Let
$n_{2}\in{\mathbb{N}}$ be such that $|p^{\prime}_{n}-p|<\epsilon/3$ for all
$n>n_{2}$.

First, consider the case that ${\mathfrak{G}}_{U(m)}\not\in{\mathcal{A}}$,
i.e. ${\mathcal{A}}$ is an $\equiv_{m}$-equivalence class distinct from that
of ${\mathfrak{G}}_{U(m)}$. In this case, our aim is to show that for all
sufficiently large $n$, in particular for all $n>\max(n_{0},n_{1},n_{2})$, we
have $p-\epsilon<p_{n}<p+\epsilon$, establishing the result. We return to the
case where ${\mathfrak{G}}_{U(m)}\in{\mathcal{A}}$ later.

Fix $n$ with $n>\max(n_{0},n_{1},n_{2})$ and let $p_{0}$ denote the
probability that $R_{n}({\mathcal{C}})$ contains _no_ component from
${\mathcal{A}}$ except those that are isomorphic to one of
$H_{1},\ldots,H_{M}$. Then clearly $p_{n}>p^{\prime}_{n}\cdot p_{0}$ since the
left-hand side denotes the probability that there are exactly $k$ components
from ${\mathcal{A}}$ and the right-hand side gives the probability of
obtaining exactly $k$ components from ${\mathcal{A}}$ in a particular way,
i.e. all from among $H_{1},\ldots,H_{M}$. Moreover $p_{0}>(1-\epsilon/3)^{2}$
since if there is a giant component with $n-g$ elements and it is
$\equiv_{m}$-equivalent to ${\mathfrak{G}}_{U(m)}$ then there cannot be a
component with more than $g$ vertices from ${\mathcal{A}}$. We then have

$\begin{array}[]{lcl}p_{n}&>&p^{\prime}_{n}p_{0}\\\
&>&p^{\prime}_{n}(1-\epsilon/3)^{2}\\\ &>&p(1-\epsilon/3)^{3}\\\
&>&p-\epsilon,\end{array}$

where the second line follows by substituting the lower bound for $p_{0}$ and
the third line follows from the fact that $|p^{\prime}_{n}-p|<\epsilon/3$.

For the other direction, note that

$p_{n}<p_{n}^{\prime\prime}p_{0}+(1-p_{n}^{\prime})(1-p_{0}),$

where the first term on the right is as above and the second term is an upper
bound on the probability that $k$ components from ${\mathcal{A}}$ are obtained
in some way other than by having $k$ components with $g$ vertices or fewer and
$0$ components with more than $g$ vertices. We then have

$\begin{array}[]{lcl}p_{n}&<&p^{\prime}_{n}p_{0}+(1-p^{\prime}_{n})(1-p_{0})\\\
&<&p^{\prime}_{n}+(1-p_{0})\\\ &<&p^{\prime}_{n}+(1-(1-\epsilon/3)^{2})\\\
&<&p+\epsilon/3+(1-(1-\epsilon/3)^{2})\\\ &<&p+\epsilon,\end{array}$

where the second line is obtained by substituting the upper bound of $1$ for
$p_{0}$ and $1-p^{\prime}_{n}$, the third line by substituting the lower bound
of $(1-\epsilon/3)^{2}$ for $p_{0}$ and the fourth by the fact that
$|p^{\prime}_{n}-p|<\epsilon/3$.

For the case that ${\mathfrak{G}}_{U(m)}\in{\mathcal{A}}$, an entirely
analogous argument can be used to show that $|p_{n}-p|<\epsilon$ where $p$ is
the limit of the sequence $p^{\prime\prime}_{n}$ of probabilities that
$R_{n}({\mathcal{C}})$ contains exactly $k-1$ components that are isomorphic
to one of $H_{1},\ldots,H_{M}$.

Fix a small addable class of graphs ${\mathcal{C}}$ and $m\in{\mathbb{N}}$.
Let $r=r_{m}(\emptyset)$ and $t=t_{m}(\emptyset)$. Suppose
${\mathcal{A}}_{1},\ldots,{\mathcal{A}}_{t}$ enumerates all the $\equiv_{m}$
classes of graphs in ${\mathcal{C}}$. We call an _$m$ -profile_ a function
$f:[t]\rightarrow\\{0,\ldots,r\\}$. We say that a graph $G$ _matches_ the
$m$-profile $f$ if the following conditions hold:

  1. 1.

for each $i\in[t]$, if $f(i)<r$ then $G$ has exactly $f(i)$ connected
components which are in ${\mathcal{A}}_{i}$; and

  2. 2.

for each $i\in[t]$, if $f(i)=r$ then $G$ has at least $r$ distinct connected
components which are in ${\mathcal{A}}_{i}$.

The following lemmas are now immediate from our previous constructions.

###### Lemma 6.4

If ${\mathcal{C}}$ is a smooth addable class of graphs then for any $m$ and
any $m$-profile $f$, the probability that $R_{n}({\mathcal{C}})$ matches $f$
converges to a value $p_{f}$ as $n$ goes to infinity.

Proof Define $p_{f}$ to be

$p_{f}=\left(\prod_{i:f(i)<r}p_{f(i)}({\mathcal{A}}_{i})\right)\left(\prod_{i:f(i)=r}\sum_{k\geq
r}p_{k}({\mathcal{A}}_{i})\right).$

The result than follows by the asymptotic independence asserted in Theorem 6.2
above.

Note that every graph matches some profile $f$ and these events are mutually
exclusive for distinct $f$. Thus, the sum of $p_{f}$ over all profiles $f$
must be $1$. The reason for considering profiles is, of course, that they
completely determine the $\equiv_{m}$ class of a graph.

###### Lemma 6.5

If $G_{1}$ and $G_{2}$ are graphs that both match the same $m$-profile $f$,
then $G_{1}\equiv_{m}G_{2}$.

Proof This is immediate from Lemma 4.1.

We can now establish the main convergence law for MSO.

###### Theorem 6.6

If ${\mathcal{C}}$ is a smooth, addable class of graphs and $\phi$ is a
sentence of MSO, then the probability that $R_{n}({\mathcal{C}})$ satisfies
$\phi$ tends to a limit as $n$ goes to infinity.

Proof Let $m$ be the quantifier rank of $\phi$. By Lemma 6.5, if $f$ is an
$m$-profile then either all graphs matching $f$ satisfy $\phi$ or none do. Let
us say that $f$ implies $\phi$ if the former case holds. Then taking $p$ to be
the sum of $p_{f}$ (as in Lemma 6.4) over all $f$ that imply $\phi$, we see
that the probability that $R_{n}({\mathcal{C}})$ satisfies $\phi$ tends to
$p$.

We can say somewhat more about the possible values $p$ to which the
probability that $\phi$ holds in $R_{n}({\mathcal{C}})$ may converge. Note
that the property of being connected is definable by a sentence of MSO and
thus the probability that $R_{n}({\mathcal{C}})$ is connected converges to a
limit. By Theorem 5.1, this value is at least $1/\sqrt{e}$ and therefore
greater than $1/2$. This, together with the result below tells us that the
limiting probabilities of MSO sentences on smooth, addable classes cluster
near $0$ and $1$.

###### Theorem 6.7

Let ${\mathcal{C}}$ be a smooth, addable class and let $c$ be the limiting
probability that $R_{n}({\mathcal{C}})$ is not connected. Then, for any MSO
sentence $\phi$, the probability that $R_{n}({\mathcal{C}})$ satisfies $\phi$
converges to a value $p$ such that either $p\leq c$ or $p\geq 1-c$.

Proof Let $m$ be the quantifier rank of $\phi$ and let ${\mathfrak{G}}_{U(m)}$
be the universal connected structure defined in Sec. 4.1. If
${\mathfrak{G}}_{U(m)}\models\phi$ then $\phi$ is true in
$R_{n}({\mathcal{C}}\cap{\rm{Conn}})$ with probability tending to $1$. Thus
the probability that $R_{n}({\mathcal{C}})$ satisfies $\phi$ tends to at least
$1-c$. On the other hand, if ${\mathfrak{G}}_{U(m)}\not\models\phi$, then
$\phi$ is false in $R_{n}({\mathcal{C}}\cap{\rm{Conn}})$ with probability
tending to $1$, and so the probability that $R_{n}({\mathcal{C}})$ satisfies
$\phi$ tends to at most $c$.

For many interesting classes of graphs, the value of $c$ is quite small. As
noted above, for planar graphs the value of $c$ is about $0.036746$, giving us
the result mentioned in the introduction.

##  7 Future work

We have shown that the zero-one law holds for random connected graphs from
smooth addable classes of graphs, for formulas of first order and monadic
second-order logic. Moreover, a limit law holds for random graphs of such
classes which do not have to be connected. This includes many of the tame
classes of graphs that have been studied in finite model theory in recent
years. Still, there are other classes one could explore. Most interesting
would be proper minor-closed classes which are not addable, such as the graphs
embeddable in a torus or, more generally, the class of graphs of genus at most
$k$ for a fixed value of $k$.

Another general direction would be to explore logics beyond first-order logic
(other than MSO) such as fixed-point logics. These are known to admit a zero-
one law over the class of all graphs. However, their study is based on
equivalence relations $\equiv^{k}$ stratified by the number of variables
rather than the quantifier rank. These equivalence relations do not have
finite index and that makes many of the methods we have used here infeasible
to use.

## References

  * [BGK07] Manuel Bodirsky, Clemens Gröpl, and Mihyun Kang.  Generating labeled planar graphs uniformly at random.  Theor. Comput. Sci., 379:377–386, July 2007.
  * [Com89] K.J. Compton.  0-1 laws in logic and combinatorics.  In I. Rival, editor, NATO Advanced Study Institute on Algorithms and Order, pages 353–383. Kluwer, 1989.
  * [CP16] Guillaume Chapuy and Guillem Perarnau.  Connectivity in bridge-addable graph classes: The McDiarmid-Steger-Welsh conjecture.  In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, pages 1580–1588, 2016.
  * [Daw07] A. Dawar.  Finite model theory on tame classes of structures.  In MFCS, volume 4708 of Lecture Notes in Computer Science, pages 2–12. Springer, 2007.
  * [DG10] A. Dawar and E. Grädel.  Properties of almost all graphs and generalized quantifiers.  Fundam. Inform., 98(4):351–372, 2010.
  * [DVW96] Alain Denise, Marcio Vasconcellos, and Dominic J. A. Welsh.  The random planar graph.  Congressus Numerantium, 113:61–79, 1996.
  * [Fag76] R. Fagin.  Probabilities on finite models.  Journal of Symbolic Logic, 41(1):50–58, March 1976.
  * [GKLT69] Y. V. Glebskiĭ, D. I. Kogan, M.I. Ligon’kiĭ, and V. A. Talanov.  Range and degree of realizability of formulas in the restricted predicate calculus.  Kibernetika, 2:17–28, 1969.
  * [GN05] Omer Giménez and Marc Noy.  Asymptotic enumeration and limit laws of planar graphs.  Mathematics of Computation, 2005.
  * [HMNT18] P. Heinig, T. Müller, M. Noy, and A. Taraz.  Logical limit laws for minor-closed classes of graphs.  J. Comb. Theory, Ser. B, 130:158–206, 2018.
  * [KV90] Ph. G. Kolaitis and M. Y. Vardi.  0-1 laws and decision problems for second-order logic.  Information and Computation, 87:302–338, 1990.
  * [KV92] Ph. G. Kolaitis and M. Y. Vardi.  Infinitary logics and 0-1 laws.  Information and Computation, 98(2):258–294, 1992.
  * [Lib04] L. Libkin.  Elements of Finite Model Theory.  Springer, 2004.
  * [Mak04] J. A. Makowsky.  Algorithmic uses of the feferman-vaught theorem.  Ann. Pure Appl. Logic, 126:159–213, 2004.
  * [McC02] Gregory L. McColm.  MSO zero-one laws on random labelled acyclic graphs.  Discrete Mathematics, 254:331–347, 2002.
  * [McD09] Colin McDiarmid.  Random graphs from a minor-closed class.  Comb. Probab. Comput., 18:583–599, July 2009.
  * [MSW05] Colin McDiarmid, Angelika Steger, and Dominic J.A. Welsh.  Random planar graphs.  Journal of Combinatorial Theory, Series B, 93(2):187 – 205, 2005\.
  * [MSW06] Colin McDiarmid, Angelika Steger, and Dominic Welsh.  Random graphs from planar and other addable classes.  In R. L. Graham, B. Korte, L. Lovász, A. Wigderson, G. M. Ziegler, Martin Klazar, Jan Kratochvíl, Martin Loebl, Jir̂í Matouŝek, Pavel Valtr, and Robin Thomas, editors, Topics in Discrete Mathematics, volume 26 of Algorithms and Combinatorics, pages 231–246. Springer Berlin Heidelberg, 2006.  10.1007/3-540-33700-8_15.