Colouring Rules for Finite Trees
and Probabilities of Monadic
Second Order Sentences
Alan R. Woods
University of Western Australia
Algorithms Seminar
March 10, 1998
[summary by Cyril Chabaud]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
Given a set of colouring rules applying to the vertices of any finite
rooted tree, we study the asymptotic behaviour of the
probability that an n vertex tree has a given root colour. These
results will prove that the fraction of labelled or unlabelled rooted
trees satisfying any fixed monadic secondorder sentence converge to
limiting probabilities.
1 Introduction
Given a finite rooted tree and a set of k colours, the vertices are
coloured from the leaves to the root according to a set of colouring
rules, namely a function h:N^{k} ®{1,2,...,k}. The
colour assigned to a vertex depends only on the number C_{1},...,C_{k} of
its immediate predecessors having colour 1,...,k.
Example 1
Let
h(C_{black},C_{white})= 
ì í î 
black 
if C_{black} is even 
white 
if C_{black} is odd 


be a set of colouring rules. From the
definition of h, the leaves of the following tree are coloured black and
we find its root colour is black.
Note that the root of a finite rooted tree is black iff the number of its
vertices is odd, with the set of colouring rules defined above.
Let µ_{n}[i] be the fraction of n vertex labelled trees with root
colour i.
Theorem 1
Let µ [i]=lim_{n®¥} µ_{n}[i] and
the corresponding Cesàro limit
For any set of colouring rules h, µ^{_}[i] exists for all
colours i=1,...,k and either

µ^{_}[i]>0 or
 $ c>1 such that µ_{n}[i]<c^{n} for all sufficiently
large n.
Although the existence of µ [i] implies the existence of
µ^{_}[i] in general, the converse needs additional conditions to be
true.
2 Applications to Logic
2.1 First Order Logic
There exists an analogous result for first order sentences about a
graph. The language in which these sentences are written contains
the usual quantifiers, parentheses
and connectives with an additional predicate symbol E(x,y)
expressing the fact that vertex x and vertex y are joined by an
edge.
Example 2
The following expression is a first order logic sentence
expressing ``every vertex has degree 2'':
" x$ y_{1}$ y_{2}(¬ y_{1}=y_{2}Ù"
z(E(x,z)Û z=y_{1}Ú z=y_{2})).
Fagin [3],
Glebskii, Kogan, Liogon'kii and Talanov [4]
have proved the following result
Proposition 1
Let µ_{n}(j) be the fraction of n vertex graphs with property
j.
For every first order sentence j about a graph,
µ(j)=lim_{n®¥} µ_{n}(j) exists and
µ(j)=0 or 1.
That the only possible values are 0,1 is a consequence of the
fact that graphs have no roots.
2.2 Monadic Second Order Logic
The situation for monadic second order sentences about a rooted tree
is quite different since the language provides a constant symbol R
denoting the root, and it can handle sets of vertices using second
order variables.
Determining the satisfiability of a monadic second order
sentence j of rank r reduces to finding the root colour of
a rooted tree T for a particular system of colouring rules.
Results arising from Compton's method of components [2]
establish that if j is a sentence of rank r, then there exists
sentences y_{1},...,y_{k} of rank r such that:

Every finite rooted tree satisfies exactly one y_{i};
 Every j of rank r is equivalent to
Ú_{iÎ S}y_{i} for some set S.
If T is a rooted tree that has component trees T_{1},..., T_{m} that satisfy sentences
y_{i}_{1},...,y_{i}_{m}, then there exists a unique i such that
T satisfies y_{i}, and this particular i can be
interpreted as the root colour of T. (For details
see [8]).
2.3 Boolean Formulas
Assume we have M boolean variables x_{1},...,x_{M}. Then the
colours turn out to be the 2^{2}^{M} boolean functions Y_{i}. The
existence of the limiting probability µ[i] is stated in the
following theorem:
Theorem 2
Let µ_{n}[i] be the fraction of formulas of size n which compute
the boolean function Y_{i}, iÎ{1,...,2^{2}^{M}}.
Then lim_{n®¥}µ_{n}[i]=µ[i] exists
and µ[i]>0.
3 Enumeration of Rooted Trees
3.1 Labelled Rooted Trees
We use generating functions methods to determine µ^{_}[i] in the
labelled case. Note that a similar proof can be done for the
unlabelled case.
Let T(x) denote the generating function for labelled rooted trees:
T(x)=t_{1}x+ 

x^{2}+ 

x^{3}+...
+ 

x^{n}+··· 
where t_{i} is the number of i vertex labelled rooted trees.
Since this structure is decomposable, we easily
obtain a functional equation on
T(x) and find:T(x)=xe^{T(x)}.
Hence, using Lagrange inversion we get:
T(x)=x+ 

x^{2}+ 

x^{3}+...
+ 

x^{n}+···. 
The radius of convergence of this series is r=1/e,
x=r is the only singularity on the circle of convergence,
where there exists a constant h_{1} such that T(x) behaves like
1+h_{1}(rx)^{1/2}. One can then
apply Darboux's theorem and find that t_{n} behaves asymptotically
like t_{n}~ Cr^{n}n^{3/2}.
3.2 Labelled Trees with a Particular Root Colour
Let T_{i}(x) be the generating function for labelled trees with root
colour i,
T_{i}(x)=x 

å 
M_{1},...,M_{k} 
h(M_{1},...,M_{k})=i 




··· 

. 
To find y_{i}=T_{i}(x) we have to solve the system:
{y_{i}=g_{i}(x,y_{1},...,y_{k})} 

where 
g_{i}(x,y_{1},...,y_{k})=x 

å 
M_{1},...,M_{k} 
h(M_{1},...,M_{k})=i 




··· 

. 
4 Cesàro Probabilities
To determine probability µ^{_}[i] we use a partial converse of
the following Abelian theorem:
Theorem 3
Let b(x)=å_{n³ 0}b_{n}x^{n}, c(x)=å_{n³ 0}c_{n}x^{n}
and r be the radius of convergence of b(x). If lim_{n®¥}c_{n}/b_{n}=µ and å_{n³ 0}
b_{n}r^{n} diverges then:
Setting c(x)=T_{i}^{'}(x) and b(x)=T^{'}(x), we find that the conditions above
are satisfied since lim_{x®r }T^{'}(x)=¥. The result is given by the following Tauberian theorem:
Theorem 4 [Compton [1]]
Let b_{n}~ Cn^{a}, a>1, b_{n}¹ 0 for n³ 0,
c_{n}=O(b_{n}). If where
r is the
radius of convergence of b(x)=å_{n³ 0} b_{n}x^{n} then:
Since
T 

(x)= 

(x,T_{i}(x),...,
T_{k}(x))+ 

T 

(x) 

(x,T_{i}(x),...,T_{k}(x)), 
when x®r , we have
Thus, the µ^{_}[i] are linearly dependent, as the following matrix
relation shows:
é ê ê ê ê ê ê ê ê ê ê ë 

ù ú ú ú ú ú ú ú ú ú ú û 

=W(r) 
é ê ê ê ê ê ê ê ê ê ê ë 

ù ú ú ú ú ú ú ú ú ú ú û 

where W(r)= 
é ê ê ê ê ê ê ê ê ê ê ë 

ù ú ú ú ú ú ú ú ú ú ú û 

, 
yielding the linear system:
(IdW(r)) ^{T}[µ^{_}[i]···µ^{_}[k]]=0.
Here W(r) is a stochastic matrix, and
from the theory of nonnegative matrices, the rank of
(IdW(r)) is k1. Consequently, the linear system above
has a unique solution satisfying µ^{_}[i]+... + µ^{_}[k]=1.
We associate with W(r) its dependency digraph D.
Namely, we put a directed edge from vertex j to vertex i iff
¶ g_{i}/¶ y_{i}(r,T_{1}(r),...,T_{k}(r
))>0.
In other words, this directed edge exists iff $
C_{1}···$ C_{k} (C_{j}>0Ù h(C_{1},...,C_{k})=i)
Property 1
There is a unique strong component S in D with the property that,
for every colour j, there is a directed edge in D from j to some
colour in S.
S is called the principal component of D.
This property is the key point to prove the first part of
theorem 1:
Theorem 5
For any system of colouring rules, µ^{_}[i] exists for all colours
i. Moreover, if S is the principal component of dependency digraph
D then
Proof.
From the property above there exist A(x) and B(x) such that
and A(x) is an irreducible matrix.
Matrix A(x) is indexed by S={1,...,s} after renumbering.
Since 1 is the largest eigenvalue of A(r), from PerronFrobenius
theory (see for instance [7])
there is a unique
normalized solution m_{1},...,m_{s} of
with m_{1}>0,...,m_{s}>0. Then we just show that 1 cannot be an
eigenvalue of B(r) and prove that [m_{1},...,m_{s},0,...,0]
is a normalized eigenvector of W (r).
The colours that do not belong to the principal component S have
probabilities that converge exponentially to zero, as the
following theorem shows:
Theorem 6
For any system of colouring rules, if iÏS then there is some
c>1 such that µ_{n}[i]<c^{n}. (The same property holds in the
unlabeled case).
Proof.[Sketch of proof]
We prove that for each i such that iÏS, T_{i}(x) has an
analytic continuation on the circle of convergence of T(x), meaning
that the radius of convergence of T_{i}(x), r_{i}, is greater than
r. Since µ_{n}[i]=t_{n}^{i}/t_{n}, this leads to desired result.
For details, see [8].
5 Existence of µ[i]
We examine here a sufficient condition to ensure the existence of
µ[i] rather than just µ^{_}[i]. The existence of µ[i] is
conditioned by the presence of a unique singularity on the circle
of convergence of T_{i}(x), indeed:
Lemma 1
Let A(x) be the irreducible block of matrix W(x). If
det(A(x)I)¹ 0 for all x¹r on the circle x=r then
µ[i] exists for all
iÎ S. The probabilities
µ[1],...,µ[s] are all strictly positive and form the unique
normalized solution of
Proof.
See [8]
If we look again the first example, clearly µ[1] and µ[2] do
not exist since series T_{black}(x) and T_{white}(x) have two
singularities on the circle x=r.
The next theorem is a sufficient criterion on colouring rules to
guarantee the convergence of µ_{n}[i]:
Theorem 7
Suppose that for each iÎ{1,...,k} there exists at least one
pair of rules of the following sort, namely:
there exists C_{1}>1,...,C_{k}>1 such that h(C_{1},...,C_{i}1,...,C_{k})=h(C_{1},...,C_{i},...,C_{k}).
Then µ[i]
exists and µ[i]>0 for all iÎ S.
Proof.[Sketch of proof]
We prove that det(IW(x))¹ 0 for all x£r except
x=r, and that each T_{i}(x) has at most x=r as a singularity
on the circle x=r.
6 Open Problems and Extensions

Characterize the asymptotic behaviour of µ_{n}[i] for general
systems of colouring rules;
 Assume j is a monadic second order sentence. For labeled
free trees, McColm [6]
proved probability µ_{n}(j) satisfied a 01 law;
 What happens when we distinguish multiple roots?
 Take unary functions y=f(x). If for some e>0 and
g>0, probability µ_{n}(j)>e/n^{g} for
infinitely many n, is there always a simple asymptotic formula for
µ_{n}(j)?
A partial answer to this last question is that µ_{n}(j)
converges, and it has been given in the labeled case
for g=0
by Compton and Shelah; Woods (also in the unlabeled case) [9];
Luczak and Thoma [5].
References
 [1]

Compton (Kevin J.). 
Application of a Tauberian theorem to finite model theory. Archiv für Mathematische Logik und Grundlagenforschung, vol. 25,
n°12, 1985, pp. 9198.
 [2]

Compton (Kevin J.). 
A logical approach to asymptotic combinatorics. II. Monadic
secondorder properties. Journal of Combinatorial Theory. Series A,
vol. 50, n°1, 1989, pp. 110131.
 [3]

Fagin (Ronald). 
Probabilities on finite models. Journal of Symbolic Logic,
vol. 41, n°1, 1976, pp. 5058.
 [4]

Glebskii (Y. V.), Kogan (D. I.), Liogon'kii (M. I.), and Talanov
(V. A.). 
Range of degree and realizability of formulas in the restricted
predicate calculus. Kibernetika (Kiev), vol. 5, n°2,
1969, pp. 1728. 
[Engl. Transl. Cybernetics, vol. 5, 142154 (1972)].
 [5]

Luczak (Tomasz) and Thoma (Lubos). 
Convergence of probabilities for the second order monadic properties
of a random mapping. Random Structures & Algorithms, vol. 11, n°3,
1997, pp. 277295.
 [6]

McColm (Gregory L.). 
MSO asymptotics on random free trees (and random strings). 
1996. Preprint.
 [7]

Minc (Henryk). 
Nonnegative matrices. 
John Wiley & Sons Inc., New York, 1988, WileyInterscience Series in Discrete Mathematics and Optimization,
xiv+206p. A WileyInterscience Publication.
 [8]

Woods (Alan R.). 
Coloring rules for finite trees, and probabilities of monadic second
order sentences. Random Structures & Algorithms, vol. 10, n°4,
1997, pp. 453485.
 [9]

Woods (Alan R.). 
Counting finite models. The Journal of Symbolic Logic, vol. 62,
n°3, 1997, pp. 925949.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.